|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
