Red and Black
2006.07.04 23:50 ACM/ICPC
[問題] ACM/ICPC Japan Domestic 2004: Problem B
[解説]
2次元グリッドにおける深さ優先探索(DFS)
プログラム例
[解説]
2次元グリッドにおける深さ優先探索(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(); }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |