3194:Equidivisions

keyword

探索　C++

概要

N*N (N<100)のボードの各セルに1~Nの数字が書かれている。同じ数字が全て連結になっているかどうか判定する問題。
探索するだけ。

char board[102][102];
int dy[] = {0,0,1,-1}, dx[] = {1,-1,0,0};
int d;

void dfs(int y, int x, int col){
    board[y][x] = ~board[y][x];
    d++;
    for(int k=0; k<4; k++){
        int ny = y + dy[k],
            nx = x + dx[k];
        if(board[ny][nx] == col)
            dfs(ny,nx,col);
    }
}

int main(){
    int i, j, x, y, n;
    while(n = readint(), n){
        REP(i,102)REP(j,102) board[i][j] = 0;
        REP(j,n-1){
            REP(i,n){
                x = readint();
                y = readint();
                board[y][x] = j+1;
            }
        }
        FOR(i,1,n+1)FOR(j,1,n+1)if(board[i][j]==0) board[i][j] = n;
        FOR(i,1,n+1)FOR(j,1,n+1)if(1 <=board[i][j] && board[i][j]<=n){
            d = 0;
            dfs(i,j,board[i][j]);
            if(d!=n){
                goto end;
            }
        }
        end:;
        if(i==n+1 && j==n+1)puts("good");
        else puts("wrong");
    }
    return 0;
}