C++の練習を兼ねて, AtCoder Regular Contest 005 の 問題C (C – 器物損壊！高橋君) を解いてみた.
■感想.
1. AtCoder Typical Contest 002 の A – 幅優先探索 に似ているように見えたが, 解けそうになかったので, ネット上の情報を探した.
2. 01-BFS で 解いていく方針が紹介されていた(※下記, 参照サイト)ので, もともとの幅優先探索のロジックを, 01-BFS用 に 書き換えた.
※但し, 書き換え前のコードを, ほとんどコメントアウトしているので, やや見づらくなってしまったように見える.
3. 新しい知識として, 01-BFS の アルゴリズム を 体感できたので, 非常に勉強になったと思う.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
// A - 幅優先探索 // https://atcoder.jp/contests/atc002 // -> 01-BFS版 に ロジック書き換え. #include <bits/stdc++.h> using namespace std; // constexpr int MAX = 400; constexpr int MAX = 250001; constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int R, C; int sx, sy, gx, gy; int board[MAX]; int memo[MAX]; // 幅優先探索(01-BFS版). // https://ja.wikipedia.org/wiki/幅優先探索 // 迷路を幅優先探索する. // ※bfsの動作確認用. // @param s: 探索開始地点の迷路上の座標. // @return: 特に無し. void bfs(int s){ // 1. 空のキュー. // ※ 01-BFS の 場合は, deque を 使うとのこと. // queue<int> q; deque<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 3. 探索地点 s をキュー q に追加. // q.push(s); q.push_back(s); while(!q.empty()){ // 4. キューから取り出す. int v = q.front(); // q.pop(); q.pop_front(); // 5. 取り出した要素を処理. // x: 列方向, y: 行方向 で考える. int nx, ny, n; int cx = v % C , cy = v / C; for(int i = 0; i < 4; ++i){ nx = cx + dx[i]; ny = cy + dy[i]; n = nx + ny * C; // cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl; // 6. 訪問不可能なマス であれば, 処理をスキップ. if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue; // --- (ここから, ロジックから除外) -------------------------------------------------------------- // if(board[n] == '#') continue; // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定. // if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n); // --- (ここまで, ロジックから除外) -------------------------------------------------------------- // 7. 壁の場合は, 距離を 1 加算. int d = 0; if(board[n] == '#') d = memo[v] + 1; else d = memo[v]; // 8. より短い経路であれば, 更新. if(memo[n] > d){ memo[n] = d; if(board[n] == '#') q.push_back(n); // 壁の場合. else q.push_front(n); // 壁でない場合. } } } return; } int main() { // 1. 入力情報取得. // cin >> R >> C >> sy >> sx >> gy >> gx; // sy--, sx--, gy--, gx--; cin >> R >> C; for(int i = 0; i < R; ++i){ string s; cin >> s; for(int j = 0; j < C; ++j){ board[i * C + j] = s[j]; // スタート地点, ゴール地点を設定. if(s[j] == 's') sx = j, sy = i; if(s[j] == 'g') gx = j, gy = i; } } // 2. 探索を開始し, 探索距離を更新. for(int i = 0; i < R * C; i++) memo[i] = 1e9; // 01-BFSで, より短い距離に更新するために必要. bfs(sy * C + sx); // for(int i = 0; i < R; ++i){ // for(int j = 0; j < C; ++j){ // cout << memo[i * C + j] << " "; // } // cout << endl; // } // 3. 出力. int ans = memo[gy * C + gx]; // cout << ans << endl; if(ans <= 2) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
[入力例] 10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g##.#.#.#. ###.#.#.#. ###.#.#.#. #.....#... [出力例(debug版)] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 2 1 0 0 0 0 1 0 1 0 3 2 1 1 1 0 1 0 1 0 2 2 1 0 1 0 1 0 1 0 3 2 1 0 1 0 1 0 1 0 2 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 YES ※AtCoderのテストケースより [入力例] 4 5 s#### ....# ##### #...g [出力例(debug版)] 0 1 1 1 2 0 0 0 0 1 1 1 1 1 2 2 1 1 1 1 YES ※AtCoderのテストケースより [入力例] 1 10 s..####..g [出力例(debug版)] 0 0 0 1 2 3 4 4 4 4 NO [入力例] 12 17 .####.####.###### s...#.####.###### ##.##.####.###### #...#.#..#.##..## ###.#.####.###.## #.....#..#.##..## #####.####.###.## #...#.#..#.##..## #####.#.##.###.## ##....#.##.###g## ##.####.##.###### ##.........#...## [出力例(debug版)] 0 1 1 1 1 0 1 2 2 1 0 1 2 3 4 5 6 0 0 0 0 1 0 1 2 2 1 0 1 2 3 4 5 6 1 1 0 1 1 0 1 2 2 1 0 1 2 3 3 4 5 1 0 0 0 1 0 1 1 1 1 0 1 2 2 2 3 4 2 1 1 0 1 0 1 2 2 1 0 1 2 3 2 3 4 1 0 0 0 0 0 1 1 1 1 0 1 2 2 2 3 4 2 1 1 1 1 0 1 1 1 1 0 1 2 3 2 3 4 2 1 1 1 1 0 1 0 0 1 0 1 2 2 2 3 4 3 2 1 1 1 0 1 0 1 1 0 1 2 3 2 3 4 2 1 0 0 0 0 1 0 1 1 0 1 2 3 2 3 4 2 1 0 1 1 1 1 0 1 1 0 1 2 2 2 3 4 2 1 0 0 0 0 0 0 0 0 0 1 1 1 1 2 3 YES |