LTF►XLor

Squares UVa201

Times：45 mins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
using namespace std;
int h[20][20] = { 0 }, v[20][20] = { 0 }, res[20] = { 0 };
int main()
{
	int kase = 0, size, T;
	while (cin >> size >> T)
	{
		memset(h, 0, sizeof h);
		memset(v, 0, sizeof v);
		memset(res, 0, sizeof res);
		while (T--)
		{
			char s;
			int x, y;
			cin >> s >> x >> y;
			if (s == 'H')
				h[x][y] = 1;
			else
				v[y][x] = 1;
		}
		int flag = 1;//标记是否完全无解
		for (int s = 1; s <= size; s++)
		{
			int cnt = 0;
			for (int i = 1; i <= size - s; i++)
				for (int j = 1; j <= size - s; j++)
				{
					int mark = 1;//标记是否缺少边
					for (int x = j; x <= j + s - 1; x++)
						if (!h[i][x] || !h[i + s][x])
							mark = 0;

					for (int x = i; x <= i + s - 1; x++)
						if (!v[x][j] || !v[x][j + s])
							mark = 0;
					if (mark)
						cnt++;
				}
			res[s] = cnt;
			if (cnt)
				flag = 0;
		}
		if(kase)
			cout << endl << "**********************************" << endl << endl;
		cout << "Problem #" << ++kase << endl << endl;
		if (flag)
			cout << "No completed squares can be found." << endl;
		for (int i = 1; i <= size; i++)
			if (res[i])
				cout << res[i] << " square (s) of size " << i << endl;
	}
	return 0;
}