読者です 読者をやめる 読者になる 読者になる

AOJ 2014 Surrounding Area

DFS AOJ C/C++ Algorithms

問題文

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;
}