PKU : 3051 - Satellite Photographs

問題概要

http://poj.org/problem?id=3051

'*' が陸を表すとします.
上下左右に'*'がつながっているひとつのグループを島とします.
このとき, 島の面積の最大を答えてください.

アルゴリズム

深さ優先探索でやるだけ.

プログラム

int w,h;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
char t[1002][100];

int dfs(int x,int y){
  int res = 1;

  t[y][x] = '.';
  rep(i,4){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(0 <= nx && nx < w && 0 <= ny && ny < h && t[ny][nx] == '*'){
      res += dfs(nx,ny);
    }
  }
  return res;
}

int main(void){
  scanf("%d%d",&w,&h);
  rep(i,h) scanf("%s",t[i]);

  int ans = 0;
  rep(i,h){
    rep(j,w){
      if(t[i][j] == '*'){
        ans = max(ans,dfs(j,i));
      }
    }
  }
  printf("%d\n",ans);
}