AOJ 2014 Surrounding Area
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2014
日本語。
解法
あるマスからDFSしていって黒に到達したら、1、白に到達したら2って感じにして行く。 dfsの再帰のところを最初+=にしようとしていた
コード
int f[50][50], c[50][50]; char l[50][51]; int w, h, dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; // black 1 white 2 int dfs(int y, int x){ if(l[y][x] == 'B') return 1; if(l[y][x] == 'W') return 2; int ret = 0; rep(d, 4){ int ny = y+dy[d], nx = x+dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w || f[ny][nx]) continue; f[ny][nx] = 1; ret |= dfs(ny, nx); } return ret; } int main(){ while(scanf("%d%d", &w, &h) && w+h){ rep(i, h) scanf("%s", l[i]); memset(c, 0, sizeof(c)); rep(i, h) rep(j, w){ if(l[i][j] == 'B' || l[i][j] == 'W' || c[i][j]) continue; memset(f, 0, sizeof(f)); f[i][j] = 1; int flag = dfs(i, j); rep(k, h) rep(m, w) if(f[k][m] != 0 && l[k][m] == '.') c[k][m] = flag; } int black = 0, white = 0; rep(i, h) rep(j, w){ if(c[i][j] == 1) black++; else if(c[i][j] == 2) white++; } printf("%d %d\n", black, white); } return 0; }