算法竞赛入门经典(第2版) 4-2UVa201 - Squares

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，20 ms）

#include<iostream>
#include<cstring>
using namespace std;
int N, M, x, y, CO[12], Times = 0;// 2 <=n<= 9,CO=Count
char SQ[12][12], ch;
inline bool V(char a) { return (a == 'B' || a == 'V' ? 1 : 0); }
inline bool H(char a) { return (a == 'B' || a == 'H' ? 1 : 0); }
int main()
{
	//freopen("in.txt", "r", stdin);
	while (~scanf("%d%d",&N,&M)) {
		getchar();
		memset(SQ, '0', sizeof(SQ));
		memset(CO, 0, sizeof(CO));
		for (int i = 0;i < M;++i) {
			scanf("%c%d%d", &ch, &x, &y);
			getchar();
			if (SQ[x][y] == '0') SQ[x][y] = ch;
			else SQ[x][y] = 'B';//Both
		}
		for (x = 1;x < N;++x) for (y = 1;y < N;++y) {
			int ml = (x > y ? N - x : N - y);//max_length,最大边长
			for (int i = 1;i <= ml;++i) {
				int j;
				for (j = 0;j < i;++j)
					if (!V(SQ[y][x + j]) || !V(SQ[y + i][x + j]) || !H(SQ[x][y + j]) || !H(SQ[x + i][y + j])) break;
				if (j == i) ++CO[i];
			}
		}
		int flag = 0;
		if(Times)printf("\n**********************************\n\n");
		printf("Problem #%d\n\n",++Times);
		for (int i = 1;i < N;++i)
			if (CO[i]) {
				printf("%d square (s) of size %d\n", CO[i],i);
				if (!flag) flag = 1;
			}
		if (!flag) printf("No completed squares can be found.\n");
	}
	return 0;
}

分析：把每个可能的正方形都枚举一遍。。比较坑的是V和H的坐标顺序是反的。