C++の練習を兼ねて, AtCoder Typical Contest 001 の 問題A (A – 深さ優先探索) を解いてみた.
■感想.
1. 前回以前に確認した 幅優先探索 の ソース を, 一部修正する形で対応した.
本家のサイトA – 深さ優先探索をご覧下さい.
■C++版プログラム(問題A／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 |
#include <bits/stdc++.h> using namespace std; // constexpr int MAX = 400; constexpr int MAX = 3e5 + 1; 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]; // 深さ優先探索. // https://ja.wikipedia.org/wiki/深さ優先探索 // 迷路を深さ優先探索する. // ※dfsの動作確認用. // @param s: 探索開始地点の迷路上の座標. // @return: 特に無し. void dfs(int s){ // 1. 空のスタック. deque<int> dq; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 3. 探索地点 s を スタック dq に追加. dq.push_front(s); while(!dq.empty()){ // 4. スタックから取り出す. int v = dq.front(); dq.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] == '.' || board[n] == 'g') && n != s && memo[n] == 0) memo[n] = memo[v] + 1, dq.push_front(n); } } return; } int main() { // 1. 入力情報取得. 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. 探索を開始し, 探索距離を更新. dfs(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 == 0) cout << "No" << endl; else cout << "Yes" << 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 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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
[入力例] 4 5 s#### ....# ##### #...g [出力例(debug版)] 0 0 0 0 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 No ※AtCoderテストケースより [入力例] 4 4 ...s .... .... .g.. [出力例(debug版)] 9 8 1 0 8 7 2 1 7 6 3 2 6 5 4 3 5 Yes ※AtCoderテストケースより [入力例] 10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g.#.#.#.#. #.#.#.#.#. ###.#.#.#. #.....#... [出力例(debug版)] 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 10 0 33 32 31 30 29 28 27 0 11 0 34 33 0 0 0 0 26 0 12 0 0 34 35 36 37 0 25 0 13 0 0 0 0 0 38 0 24 0 14 0 0 0 47 0 39 0 23 0 15 0 0 0 46 0 40 0 22 0 16 0 0 0 45 0 41 0 21 0 17 0 46 45 44 43 42 0 20 19 18 0 No ※AtCoderテストケースより [入力例] 10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g.#.#.#.#. #.#.#.#.#. #.#.#.#.#. #.....#... [出力例(debug版)] 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 10 0 33 32 31 30 29 28 27 0 11 0 34 33 0 0 0 0 26 0 12 0 0 34 35 36 37 0 25 0 13 0 0 0 0 0 38 0 24 0 14 50 49 0 47 0 39 0 23 0 15 0 48 0 46 0 40 0 22 0 16 0 47 0 45 0 41 0 21 0 17 0 46 45 44 43 42 0 20 19 18 50 Yes ※AtCoderテストケースより [入力例] 1 10 s..####..g [出力例(debug版)] 0 1 2 0 0 0 0 0 0 0 0 No ※AtCoderテストケースより [入力例] 16 12 s.########## #.##......## #.##.#.##.## #....#....## ##.######### ##..######## ###.######## ###......### ###.####..## ###.##.....# ###.####.#.# ###.##.#.#.# ###.####.#.# ###.###..### ###.#..#..g# ###......### [出力例(debug版)] 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 9 10 11 12 19 18 0 0 0 3 0 0 8 0 12 0 0 17 0 0 0 4 5 6 7 0 13 14 15 16 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 7 8 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 10 11 34 33 32 31 0 0 0 0 0 0 11 0 0 0 0 30 31 0 0 0 0 0 12 0 0 31 30 29 30 31 0 0 0 0 13 0 0 0 0 28 0 32 0 0 0 0 14 0 0 0 0 27 0 33 0 0 0 0 15 0 0 0 0 26 0 34 0 0 0 0 16 0 0 0 26 25 0 0 0 0 0 0 17 0 21 22 0 24 25 26 0 0 0 0 18 19 20 21 22 23 0 0 0 26 Yes |
■参照サイト
AtCoder Typical Contest 001