89 lines
3.1 KiB
C++
89 lines
3.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
//这个结构体有意思，描述的意义就多了一个维度
|
||
struct point {
|
||
int h;
|
||
int v;
|
||
} xian[10][10];
|
||
|
||
/**
|
||
* 功能：计算在指定 长=chang, 横=hen,竖=shu 情况下，有多少个正方形 *
|
||
* @param chang
|
||
* @param hen
|
||
* @param shu
|
||
* @return
|
||
*/
|
||
int jisuan(int chang, int hen, int shu) {
|
||
//因为前面判断了，所以这里加上chang，肯定不会出界
|
||
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
|
||
|
||
//挨个加上去，看看中间是不是全都有线存在
|
||
for (int i = 0; i < chang; i++) {
|
||
x1 += xian[hen][shu + i].h; //开始行，是不是有线
|
||
x2 += xian[hen + chang][shu + i].h; //结束行，是不是有线
|
||
|
||
y1 += xian[hen + i][shu].v; //开始列，是不是有线
|
||
y2 += xian[hen + i][shu + chang].v; //结束列，是不是有线
|
||
}
|
||
if (x1 + x2 + y1 + y2 == 4 * chang)
|
||
return 1;
|
||
else
|
||
return 0;
|
||
}
|
||
|
||
|
||
int main() {
|
||
int dian, n, kase = 1;
|
||
char direction;
|
||
int a, b;
|
||
//第一行会给出这个正方形矩阵的每一行由n个点组成(2<=n <= 9) --->dian
|
||
//第二行会给出要输入的边的数据 --->n
|
||
while (scanf("%d%d", &dian, &n) == 2) {
|
||
// 第一行不打印星星
|
||
if (kase != 1)
|
||
printf("\n**********************************\n\n");
|
||
|
||
//正方形的数组进行初始化
|
||
for (int p = 1; p <= dian; p++)
|
||
for (int q = 1; q <= dian; q++) {
|
||
xian[p][q].h = 0;
|
||
xian[p][q].v = 0;
|
||
}
|
||
while (n--)//输入全部数据
|
||
{
|
||
getchar();
|
||
scanf("%c", &direction); // H or V
|
||
if (direction == 'H') {
|
||
scanf("%d%d", &a, &b);
|
||
xian[a][b].h = 1; //表示:从a到b 存在一个水平的线
|
||
} else {
|
||
scanf("%d%d", &a, &b);
|
||
xian[b][a].v = 1; //表示:从b到a 存在一个垂直的线,注意这里是b,a，是反着的,注意看题，是这样给数据的！紫书这里说的不清晰。
|
||
}
|
||
}
|
||
|
||
printf("Problem #%d\n\n", kase++);
|
||
int k, i, p, q, ji = 0;
|
||
for (i = 1; i < dian; i++)// 几个长度的正方形？ 比如边形为1，2，3的分别计算
|
||
{
|
||
k = 0; //正方形计数器
|
||
for (p = 1; p <= dian; p++) //两层循环为遍历原始的正方形
|
||
for (q = 1; q <= dian; q++) {
|
||
//如果超出了，就不要了，分别判断横向与纵向两种情况
|
||
if ((p + i) > dian || (q + i) > dian)
|
||
break;
|
||
//判断函数，在i=边形，p=横向,q=纵向，能否构成正方形？
|
||
k += jisuan(i, p, q);
|
||
}
|
||
if (k != 0) {
|
||
ji = 1; //找到答案，输出答案
|
||
printf("%d square (s) of size %d\n", k, i);
|
||
}
|
||
}
|
||
//一个答案都没有~
|
||
if (ji == 0)
|
||
printf("No completed squares can be found.\n");
|
||
}
|
||
return 0;
|
||
}
|