You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

89 lines
3.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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++)// 几个长度的正方形? 比如边形为123的分别计算
{
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;
}