計算給定的區域不同種類的坑洞的面積，輸出時依照坑洞面積的大小排序，如果一樣則按照字母順序。
想法：
碰到不是'.'的字元就用BFS去算該坑洞的面積，最後再sort輸出即可。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <queue> | |
| #include <algorithm> | |
| using namespace std; | |
| int X, Y; | |
| char grid[55][55]; | |
| struct hole_type { | |
| char ch; | |
| int num; | |
| }hole[2550]; | |
| struct point_type { | |
| int i; | |
| int j; | |
| }; | |
| hole_type BFS(char c, int i, int j); | |
| bool cmp(hole_type a, hole_type b); | |
| int main() | |
| { | |
| // freopen("input.txt","rt",stdin); | |
| int Case = 1; | |
| while (scanf("%d%d", &X, &Y) && (X || Y)) { | |
| for (int i = 0; i < X; ++i) | |
| scanf("%s", grid[i]); | |
| int numOfhole = 0; | |
| for (int i = 0; i < X; ++i) | |
| for (int j = 0; j < Y; ++j) | |
| if (grid[i][j] != '.') | |
| hole[numOfhole++] = BFS(grid[i][j], i, j); | |
| sort(hole, hole + numOfhole, cmp); | |
| printf("Problem %d:\n", Case++); | |
| for (int i = 0; i < numOfhole; ++i) | |
| printf("%c %d\n", hole[i].ch, hole[i].num); | |
| } | |
| } | |
| const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; | |
| hole_type BFS(char c, int i, int j) | |
| { | |
| queue<point_type> Q; | |
| Q.push({i,j}); | |
| grid[i][j] = '.'; | |
| int num = 1; | |
| point_type cur, nxt; | |
| while (!Q.empty()) { | |
| cur = Q.front(); | |
| Q.pop(); | |
| for (int k = 0; k < 4; ++k) { | |
| nxt.i = cur.i + direction[k][0]; | |
| nxt.j = cur.j + direction[k][1]; | |
| if (nxt.i < 0 || nxt.i >= X || nxt.j < 0 || nxt.j >= Y) continue; | |
| if (grid[nxt.i][nxt.j] == c) { | |
| grid[nxt.i][nxt.j] = '.'; | |
| Q.push(nxt); | |
| ++num; | |
| } | |
| } | |
| } | |
| return {c, num}; | |
| } | |
| bool cmp(hole_type a, hole_type b) | |
| { | |
| return (a.num == b.num) ? (a.ch < b.ch) : (a.num > b.num); | |
| } |
沒有留言:
張貼留言