1 条题解
-
0
题目描述
儿童棋盘游戏由一个方形的点数组组成,其中包含连接一些点的线条。游戏的一部分要求玩家计算这些线形成的正方形数。例如,在下图中,有3个平方,2个大小为1,大小为2,因此平方总数为3。(正方形的“大小”是形成侧面所需的线段数。
你的任务是写一个程序来计算所有可能的正方形的数量。 输入
输入代表一系列游戏板。每个板由一个平方数组的n ^ 2个点(其中2 <= n <= 1500)和一些相互连接的水平和垂直线组成。具有n ^ 2个点和m(m <=30000)互连行的单个板的记录如下:
第1行:“n”单行或列中的点数。
第2行:“m”互连线路数。
下一个 m 行是以下两种类型之一:
“H i j k”(1 <= i,j <= n,k >0,j + k <= n)表示从行i中的点的水平长度k,列j到行i中的点,列j到行i中的点,列j。
或
“V i j k”(1 <= i,j <= n,k >0,i + k <= n)表示长度k的垂直行,从行i,列j到行i + k,列j到行中的点。
输入的结束用文件结尾表示。
输出:
对于每个记录,打印只有一个整数,即平方数。 输入数 1
#include <algorithm> #include <iostream> #include <queue> #include <cmath> #include <set> #include <vector> #include <string> #include <sstream> #include <ctype.h> #include <string.h> using namespace std; const int N = 10; const int INF = 1000000; int hor[N][N]; int ver[N][N]; int main() { // freopen("in.txt", "r", stdin); int T = 0, dot, edge, x, y, ans[15], Case = 1; char c[5]; while(~scanf("%d%d", &dot, &edge)) { memset(hor, 0, sizeof(hor)); memset(ver, 0, sizeof(ver)); memset(ans, 0, sizeof(ans)); while(edge --) { cin >> c; scanf("%d%d", &x, &y); if(c[0] == 'H') hor[x][y] = 1; else if(c[0] == 'V') ver[y][x] = 1; } int sta = dot - 1;//标准化 if(T ++) printf("\n**********************************\n\n"); /* for(int i = 1; i <= dot; i ++) { for(int j = 1; j <= sta; j ++) printf("%d ", hor[i][j]); printf("\n"); } for(int i = 1; i <= sta; i ++) { for(int j = 1; j <= dot; j ++) printf("%d ", ver[i][j]); printf("\n"); }*/ for(int i = 1; i <= sta; i ++) //边长度的延伸 { for(int j = 1; j + i <= dot; j ++)//判断行 { for(int k = 1; k + i <= dot; k ++)//判断列 { int flag = 1; for(int l = 0; l <= i; l += i) for(int m = 0; m <= i - 1; m ++) { if(hor[j + l][k + m] == 0) { flag = 0; // printf("fuck1"); // printf("fuck1---<%d, %d>\n", j + l, k + m); break; } } for(int l = 0; l <= i - 1; l ++) for(int m = 0; m <= i; m += i) { if(ver[j + l][k + m] == 0) { flag = 0; // printf("fuck2---<%d, %d>\n", j + l, k + m); break; } } if(flag == 1) { ans[i] ++;/* printf("可行解:<%d, %d>\n", j, k); */} } } } printf("Problem #%d\n\n", Case ++); int flag1 = 0; for(int i = 1; i <= sta; i ++) { if(ans[i]) { printf("%d square (s) of size %d\n", ans[i], i); flag1 = 1; } } if(!flag1) printf("No completed squares can be found.\n"); } return 0; }
- 1
信息
- ID
- 1446
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 0
- 上传者