Red and Black

[問題] ACM/ICPC Japan Domestic 2004: Problem B

[解説]
２次元グリッドにおける深さ優先探索(DFS)

プログラム例

// @author yutaka C++
#include<iostream>
#define MAX 20

using namespace std;

int row, column, si, sj, sum;
char G[MAX+2][MAX+2];
bool visited[MAX+2][MAX+2];

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

void recursive( int i, int j ){
    sum++;
    visited[i][j] = true;
    
    int ni, nj;
    for ( int r = 0; r < 4; r++ ){
        ni = i + dx[r];
        nj = j + dy[r];
        if ( G[ni][nj] == '.' && !visited[ni][nj] ) recursive(ni, nj);
    }
}

void compute(){
    sum = 0;
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            visited[i][j] = false;
        }
    }
    
    recursive(si, sj);
    
    cout << sum << endl;
}

bool input(){
    cin >> column >> row;
    if ( row == 0 && column == 0 ) return false;
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            cin >> G[i][j];
            if ( G[i][j] == '@' ){
                G[i][j] = '.';
                si = i; sj = j;
            }
        }
    }
    for ( int i = 0; i < row + 2; i++ ) G[i][0] = G[i][column + 1] = '#';
    for ( int j = 0; j < column + 2; j++ ) G[0][j] = G[row+1][j] = '#';
    
    return true;
}

main(){
    while ( input() ) compute();
}