2263 - The Castle
Figure 1 shows the map of a castle. Write a program that calculates
<span>1. how many rooms the castle has</span>
<span>2. how big the largest room is</span>
<span>The castle is divided into m * n (m<=50, n<=50) square modules. Each such module can have between zero and four walls.</span>
<img alt="" src="http://tk.hustoj.com:80/attached/image/20131210/20131210184301_17138.png" />
<span style="font-family:Consolas;">#<span> </span>= Wall<span> </span></span>
<span style="font-family:Consolas;">|<span> </span>= No wall</span>
<span style="font-family:Consolas;">-<span> </span>= No wall</span>
Input
Your program is to read from standard input. The first line contains the number of modules in the north-south direction and the second line contains the number of modules in the east-west direction. In the following lines each module is described by a number (0 <= p <= 15). This number is the sum of: 1 (= wall to the west), 2 (= wall to the north), 4 (= wall to the east), 8 (= wall to the south). Inner walls are defined twice; a wall to the south in module (1, 1) is also indicated as a wall to the north in module (2, 1). The castle always has at least two rooms
Output
Your program is to write to standard output: First the number of rooms, then the area of the largest room (counted in modules).
Examples
Input
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13
Output
5 9
Solution C++
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 60, M = 100010; int n, m, p; int a[N][N][4]; bool b[N][N]; int q[M][3]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int maxx = -1, tot; void bfs(int x, int y){ memset(q, 0, sizeof q); tot ++; int tail = 1, head = 0, xx, yy; q[1][1] = x, q[1][2] = y; while (head < tail){ head ++; for (int i = 0; i < 4; i ++){ xx = q[head][1] + dx[i]; yy = q[head][2] + dy[i]; if (xx > 0 && xx <= n && yy > 0 && yy <= m && b[xx][yy] && a[q[head][1]][q[head][2]][i] == 0){ tail ++; b[xx][yy] = false; q[tail][1] = xx; q[tail][2] = yy; } } } maxx = max(tail - 1, maxx); } int main(){ memset(b, true, sizeof b); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++){ scanf("%d", &p); if (p >= 8) { p -= 8; a[i][j][1] = 1; } if (p >= 4) { p -= 4; a[i][j][3] = 1; } if (p >= 2){ p -= 2; a[i][j][0] = 1; } if (p >= 1) { p -= 1; a[i][j][2] = 1; } } for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (b[i][j]) bfs(i, j); printf("%d\n%d\n", tot, maxx); return 0; }