Squares
Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown
Accepted Code
// Author : Weihao Long// Created : 2018/01/02#include "stdio.h"#include "string.h"struct node { int flagh; // 该点下方是否有线 int flagv; // 该点右边是否有线};int main() { int n, m; int count = 0; while (scanf("%d%d", &n, &m) != EOF) { getchar(); count += 1; int ans[10] = { 0 }; node a[10][10]; memset(a, 0, sizeof(a)); for (int i = 0; i < m; i++) { //录入数据 char ch = getchar(); int x, y; if (ch == 'H') { scanf("%d%d", &x, &y); a[x][y].flagh = 1; } else if (ch == 'V') { scanf("%d%d", &y, &x); a[x][y].flagv = 1; } getchar(); } for (int i = 1; i < n; i++) { // 控制扫描规格 for (int k = 1; k <= n - i; k++) { // 控制行 int limv = k + i - 1; // 垂直最深处 for (int t = 1; t <= n - i; t++) { // 控制列 int limh = t + i - 1; // 水平最远处 int flag = 1; int kk = k, tt = t; // 回型检查是否有线 for (; kk <= limv && flag; kk++) { if (!a[kk][tt].flagv) flag = 0; } for (; tt <= limh && flag; tt++) { if (!a[kk][tt].flagh) flag = 0; } kk -= 1; for (; kk >= k && flag; kk--) { if (!a[kk][tt].flagv) flag = 0; } kk += 1; tt -= 1; for (; tt >= t && flag; tt--) { if (!a[kk][tt].flagh) flag = 0; } if (flag) { ans[i] += 1; } } } } int tag = 0; // 检查是否有解 for (int i = 1; i < n; i++) { if (ans[i]) { tag = 1; break; } } if (count != 1) { printf("\n**********************************\n\n"); } printf("Problem #%d\n\n", count); if (tag) { for (int i = 1; i < n; i++) { if (ans[i]) { printf("%d square (s) of size %d\n", ans[i], i); } } } else { printf("No completed squares can be found.\n"); } } return 0;} Notes
题意：
有 n 行 n 列的小黑点，还有 m 条线段连接其中的一些黑点。统计这些线连成了多少个正方形（每种边长分别统计）。思路：
定义一个描述节点的结构，描述它的右边和下方是否有线。按题意模拟扫描过程即可。算法：
第一步：录入数据时，把连线的过程简化成描述该点的右边和下方是否有线。第二步：扫描正方形：首先确定规格，然后确定起始点（即左上角的点），最后转一个回型检查是否全都有线。感受：
输入的时候要注意吸收回车符。输入纵向的线注意横纵坐标的先后。扫描的过程要先想清楚循环怎么套再下手。走点的时候要注意何时该把点往回拉。