问题描述
p201原题链接：UVaOJ 201 - Square
相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-2
解法一：模拟
遍历每个点进行判断，看以这个点 [x][y] 作为左上角可以得到多少个正方形：对于大小为 l 的正方形，只需要满足三个起点（左上、左下、右上）能够延伸出长度为 l 的边就行了。
|
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 56 |
#include <bits/stdc++.h> using namespace std; int h[10][10], v[10][10], s[10]; bool has_h(int x, int y, int l) { for (int p = 0; p < l; ++p) if (h[x][y + p] != 1) return false; return true; } bool has_v(int x, int y, int l) { for (int p = 0; p < l; ++p) if (v[x + p][y] != 1) return false; return true; } void count_square(int x, int y, int max_l) { for (int l = 1; l <= max_l; ++l) { if (has_h(x, y, l) && has_h(x + l, y, l) && has_v(x, y, l) && has_v(x, y + l, l)) s[l] += 1; } } int main() { int n, m, tmp, x, y, problem_num = 0; string dir; while (cin >> n) { if (problem_num) cout << endl << "**********************************" << endl << endl; cout << "Problem #" << ++problem_num << endl << endl; memset(h, 0, sizeof(h)); memset(v, 0, sizeof(v)); memset(s, 0, sizeof(s)); cin >> m; while (m--) { cin >> dir >> x >> y; if (dir == "H") h[x][y] = 1; if (dir == "V") v[y][x] = 1; } for (int i = 1; i < n; ++i) for (int j = 1; j < n; ++j) count_square(i, j, n - max(i, j)); int total_num = 0; for (int i = 1; i < n; ++i) { if (s[i]) cout << s[i] << " square (s) of size " << i << endl; total_num += s[i]; } if (!total_num) cout << "No completed squares can be found." << endl; } return 0; } |
|
1 |
#TODO |
