日々精進

aikoと旅行とプログラミング

【AOJ 2014】Surrounding Area

問題

Surrounding Area | Aizu Online Judge

方針

  • 白い杭から探索した場合には黒い杭, 黒い杭から探索した場合は白い杭に当たるまでひたすら探索
  • 黒だけで塗りつぶされた場所と白だけで塗りつぶされた場所を数える.

コード

#include <iostream>
#include <utility>

using namespace std;

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

int w, h;
bool black[51][51];
bool white[51][51];
string field[51];

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};

void solve(int x, int y, char c){
  
  if((c == 'B' && black[y][x]) || (c == 'W' && white[y][x])) return;

  if(c == 'W' && field[y][x]!='W') white[y][x] = true;
  else if(c == 'B' && field[y][x]!='B') black[y][x] = true;
  
  rep(i, 4){
    int nx = x + dx[i]; int ny = y + dy[i];    
    if(0 <= nx && nx < w && 0 <= ny && ny < h && field[ny][nx] == '.'){
      solve(nx, ny, c);
    }
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(cin >> w >> h, w || h){

    rep(i, h){
      cin >> field[i];
    }

    fill(black[0], black[50], false);
    fill(white[0], white[50], false);

    rep(i, h){
      rep(j, w){
    if(field[i][j] == 'W') {
      solve(j, i, 'W');
    }else if(field[i][j] == 'B'){
      solve(j, i, 'B');
    }
      }
    }
    
    int bl, wh;
    bl = wh = 0;

    rep(i, h){
      rep(j, w){
    if(black[i][j] && !white[i][j]) bl++;
    else if(!black[i][j] && white[i][j]) wh++;
      }
    }
  
    cout << bl << " " << wh << endl;
  }
  
}

ソースコードめちゃくちゃ汚い気がする…