3051:Satellite Photographs

keyword

DFS　C++

概要

ボード(1000*80以下)が与えられる。各セルは牧草地であるかそうでないかの2種類。牧草地が繋がっているのをひとまとめにして考えるとき、最大のクラスタの大きさを求める問題。
よくある探索の問題。書くだけなのにWAくらってびっくり。配列のインデックスを逆にしていたことに気付く。board[y][x]の形式に自分を慣らしておかないと。

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

void dfs(int x, int y){
    if(x<0||w<=x||y<0||h<=y || board[y][x]!='*'){
        best = max(cnt, best);
        return ;
    }
    cnt++;
    board[y][x] = '.';
    int i;
    REP(i,4)dfs(x+dx[i],y+dy[i]);
    return ;
}

int main(){
    int i,j;
    best = 0;

    scanf("%d%d\n",&w,&h);
    REP(i,h){
        scanf("%s\n",board[i]);
    }

    REP(i,h)REP(j,w){
        cnt = 0;
        dfs(j,i);
    }

    printf("%d\n",best);
    return 0;
}