AOJの1130、Red and Blackをc++で解きました。
よくあるグリッド系の問題ですが、初めてこれ系の解きました。
これでfor文でゴリ押し出来ない問題が解けるようになりました。
今回は練習がてらに
幅優先探索・深さ優先探索どちらでも解いてみました。
DPでも解けるそうですが、イマイチDPは書き方が分かりません。。。
問題文はこちら
| // 横型探索 | |
| #include <iostream> | |
| #include <string> | |
| #include <vector> | |
| #include <queue> | |
| using namespace std; | |
| int w, h; | |
| int mx[] = {0, 0, -1, 1}; | |
| int my[] = {-1, 1, 0, 0}; | |
| int main() { | |
| while ( true ) { | |
| int x, y, cnt = 0; | |
| cin >> w >> h; | |
| if ( w == 0 && h == 0 ) break; | |
| vector<string> v(h); | |
| queue<int> s; | |
| for ( int i = 0; i < h; i++ ) { | |
| cin >> v[i]; | |
| // @の座標を記録 | |
| for ( int j = 0; j < v[i].size(); j++ ) { | |
| if ( v[i][j] == '@' ) { | |
| y = i; | |
| x = j; | |
| } | |
| } | |
| } | |
| // キューにスタート地点を追加 | |
| s.push(x); | |
| s.push(y); | |
| while(!s.empty()) { | |
| x = s.front(); s.pop(); | |
| y = s.front(); s.pop(); | |
| for ( int i = 0; i < 4; i++ ) { | |
| int nx = x + mx[i], ny = y + my[i]; | |
| if ( 0 <= nx && nx < w && 0 <= ny && ny < h && v[ny][nx] == '.' ) { | |
| v[ny][nx] = '#'; | |
| s.push(nx); | |
| s.push(ny); | |
| } | |
| } | |
| cnt++; | |
| } | |
| cout << cnt << endl; | |
| } | |
| return 0; | |
| } |
| // 縦型探索 | |
| #include <iostream> | |
| #include <string> | |
| #include <vector> | |
| using namespace std; | |
| int w, h; | |
| int mx[] = {0, 0, -1, 1}; | |
| int my[] = {-1, 1, 0, 0}; | |
| int dfs(int x, int y, vector<string> &v) { | |
| int cnt = 1; | |
| for ( int i = 0; i < 4; i++ ) { | |
| int nx = x + mx[i], ny = y + my[i]; | |
| if ( 0 <= nx && nx < w && 0 <= ny && ny < h && v[ny][nx] == '.' ) { | |
| v[ny][nx] = '#'; | |
| cnt += dfs(nx, ny, v); | |
| } | |
| } | |
| return cnt; | |
| } | |
| int main() { | |
| while ( true ) { | |
| int x, y; | |
| cin >> w >> h; | |
| if ( w == 0 && h == 0 ) break; | |
| vector<string> v(h); | |
| for ( int i = 0; i < h; i++ ) { | |
| cin >> v[i]; | |
| for ( int j = 0; j < v[i].size(); j++ ) { | |
| if ( v[i][j] == '@' ) { | |
| y = i; | |
| x = j; | |
| } | |
| } | |
| } | |
| cout << dfs(x, y, v) << endl; | |
| } | |
| return 0; | |
| } |