A children’s board game consists of a square array of dots that contains lines connecting some of the pairs of adjacent dots. One part of the game requires that the players count the number of squares of certain sizes that are formed by these lines. For example, in the figure shown below, there are 3 squares — 2 of size 1 and 1 of size 2. (The “size” of a square is the number of lines segments required to form a side.)
Your problem is to write a program that automates the process of counting all the possible squares.
Input
The input file represents a series of game boards. Each board consists of a description of a square array of n 2 dots (where 2 ≤ n ≤ 9) and some interconnecting horizontal and vertical lines. A record for a single board with n 2 dots and m interconnecting lines is formatted as follows:
Line 1: n the number of dots in a single row or column of the array
Line 2: m the number of interconnecting lines
Each of the next m lines are of one of two types:
H i j indicates a horizontal line in row i which connects the dot in column j to the one to its right in column j + 1
V i j indicates a vertical line in column i which connects the dot in row j to the one below in row j + 1
Information for each line begins in column 1. The end of input is indicated by end-of-file. The first record of the sample input below represents the board of the square above.
Output
For each record, label the corresponding output with ‘Problem #1’, ‘Problem #2’, and so forth. Output for a record consists of the number of squares of each size on the board, from the smallest to the largest. lf no squares of any size exist, your program should print an appropriate message indicating so. Separate output for successive input records by a line of asterisks between two blank lines, like in the sample below.
Sample Input
4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
Sample Output
Problem #1
2 square (s) of size 1
1 square (s) of size 2
**********************************
Problem #2
No completed squares can be found.
题目类型：简单模拟
算法分析：构造一个链接点与点之间关系的图，然后从小到大枚举每一个可能的子正方形的边长，按照从上至下，从左至右的顺序以每一个元素的位置为起始位置来”构造”相应边长的子正方形。注意最后一个测试用例的最后没有多余的空行。输出多余的空行在UVA上会WA，下面第一个代码是更好的实现
|
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
/************************************************** filename :l.cpp author :maksyuki created time :2017/12/8 20:01:15 last modified :2017/12/8 20:28:59 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; bool g[12][12][12][12]; int main() { #ifdef LOCAL CFF; CFO; #endif int n, m, id = 1; while(scanf("%d", &n) != EOF) { scanf(" %d", &m); memset(g, false, sizeof(g)); char ch; int ix, iy; for(int i = 1; i <= m; i++) { scanf(" %c %d %d", &ch, &ix, &iy); if(ch == 'H') g[ix][iy][ix][iy+1] = true; else g[iy][ix][iy+1][ix] = true; } int ans[16]; memset(ans, 0, sizeof(ans)); for(int len = 1; len <= n - 1; len++) for(int i = 1; i <= n - len; i++) for(int j = 1; j <= n - len; j++) { bool is_valid = true; for(int q = j; q <= j + len - 1; q++) if(!g[i][q][i][q+1] || !g[i+len][q][i+len][q+1]) { is_valid = false; break; } for(int q = i; q <= i + len - 1; q++) if(!g[q][j][q+1][j] || !g[q][j+len][q+1][j+len]) { is_valid = false; break; } if(is_valid) ans[len]++; } if(id > 1) printf("\n**********************************\n\n"); printf("Problem #%d\n\n", id++); bool is_have = false; for(int i = 1; i <= n - 1; i++) if(ans[i]) { is_have = true; break; } if(!is_have) puts("No completed squares can be found."); else { for(int i = 1; i <= n - 1; i++) if(ans[i]) printf("%d square (s) of size %d\n", ans[i], i); } } return 0; } |
|
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include <iostream> #include <fstream> #include <cstring> using namespace std; const int maxn = 16; int cnt[16]; int side, flag = 1; struct point { bool edge[4]; //edge[0] means "up edge" 1, 2, 3 mean left, down, right edge" }; point ans[maxn][maxn]; bool OkMove (int x, int y) { if (x >= 0 && x <= side - 1 && y >= 0 && y <= side - 1) return true; return false; } bool Search (int x, int y, int len) { int i; bool can = true; for (i = 1; i <= len; i++) { if (OkMove (x, y + 1) && ans[x][y].edge[1]) y++; else can = false; } for (i = 1; i <= len; i++) { if (OkMove (x + 1, y) && ans[x][y].edge[2]) x++; else can = false; } for (i = 1; i <= len; i++) { if (OkMove (x, y - 1) && ans[x][y].edge[3]) y--; else can = false; } for (i = 1; i <= len; i++) { if (OkMove (x - 1, y) && ans[x][y].edge[0]) x--; else can = false; } return can; } int main() { // ifstream cin ("aaa.txt"); bool is_illegal; char oper; int weizhi_x, weizhi_y; while (cin >> side) { int side_num; cin >> side_num; memset (cnt, 0, sizeof (cnt)); is_illegal = true; int i; for (i = 0; i < maxn; i++) { int j; for (j = 0; j < maxn; j++) memset (ans[i][j].edge, false, sizeof (ans[i][j].edge)); } for (i = 0; i < side_num; i++) { cin >> oper >> weizhi_x >> weizhi_y; if (oper == 'H') { ans[weizhi_x-1][weizhi_y-1].edge[1] = true; ans[weizhi_x-1][weizhi_y].edge[3] = true; } else if (oper == 'V') { ans[weizhi_y-1][weizhi_x-1].edge[2] = true; ans[weizhi_y][weizhi_x-1].edge[0] = true; } } for (i = 1; i <= side - 1; i++) { int j, k; for (j = 0; j < side; j++) for (k = 0; k < side; k++) if (Search (j, k, i)) { cnt[i]++; is_illegal = false; } } if (flag - 1) cout << endl << "**********************************" << endl << endl; cout << "Problem #" << flag++ << endl << endl; if (is_illegal) cout << "No completed squares can be found." << endl; else { for (i = 1; i <= side - 1; i++) if (cnt[i]) cout << cnt[i] << " square (s) of size " << i << endl; } } return 0; } |
- « 上一篇：uva1589
- uva220：下一篇 »