usaco2.1.1-----the castle（flood fill模型）

/* ID:lvfuan11 PROG:castle LANG:C++ translation: 见usanocow solution: flood fill的经典模型。dfs即可。注意题目要求选择最靠西边的墙，意味着同一个各自内，该格的北墙的优先级是比西墙高的！ 因为北墙更靠近西边。 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 55; const int dir_row[] = {-1, 1, 0, 0}; const int dir_col[] = {0, 0, -1, 1}; //上下左右 int mat[maxn][maxn], n, m; int vis[maxn][maxn], area[maxn*maxn]; bool wall[maxn][maxn][4]; bool isWall(int r, int c, int d) { if(d == 0 && mat[r][c] & 2) return true; if(d == 1 && mat[r][c] & 8) return true; if(d == 2 && mat[r][c] & 1) return true; if(d == 3 && mat[r][c] & 4) return true; return false; } inline bool inside(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } void dfs(int r, int c, int tag) { vis[r][c] = tag; for(int d = 0; d < 4; d++) { int nr = r + dir_row[d]; int nc = c + dir_col[d]; if(inside(nr, nc) && vis[nr][nc] < 0 && !isWall(r, c, d)) dfs(nr, nc, tag); } } int main() { freopen("castle.in", "r", stdin); freopen("castle.out", "w", stdout); while(~scanf("%d%d", &m, &n)) { //n行m列 memset(vis, -1, sizeof(vis)); memset(wall, 0, sizeof(wall)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &mat[i][j]); } } int id = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) if(vis[i][j] < 0) { dfs(i, j, id++); } } int maxArea = 0; memset(area, 0, sizeof(area)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { area[vis[i][j]]++; maxArea = max(maxArea, area[vis[i][j]]); } } int ans = 0, row, col; char dir; for(int j = 0; j < m; j++) { //注意遍历的顺序 for(int i = n-1; i >= 0; i--) { int currRoom = vis[i][j], northRoom = -1, eastRoom = -1; if(i > 0) northRoom = vis[i-1][j]; if(j < m - 1) eastRoom = vis[i][j+1]; if(northRoom != -1 && currRoom != northRoom && area[currRoom] + area[northRoom] > ans) { ans = area[currRoom] + area[northRoom]; row = i; col = j; dir = 'N'; } if(eastRoom != -1 && currRoom != eastRoom && area[currRoom] + area[eastRoom] > ans) { ans = area[currRoom] + area[eastRoom]; row = i; col = j; dir = 'E'; } } } printf("%d\n%d\n%d\n%d %d %c\n", id, maxArea, ans, row + 1, col + 1, dir); } return 0; }