C++の練習を兼ねて, AtCoder Typical Contest 002 の 問題A (A – 幅優先探索) を解いてみた.
■感想.
1. 幅優先探索 に 慣れるために, コーディングしたが, ACを取れるまで苦労した.
具体的には, 以下のような原因で, 探索イメージ と 実際の探索状況 が ズレてしまっていた.
※探索開始地点, 探索終了地点 の index が 1ずつズレていた点, 探索距離の更新方法がおかしかった点.
2. 未使用の変数, コメント誤りなどがあったので, 前回の投稿から, 一部差し替えた.
本家のサイト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 |
#include <bits/stdc++.h> using namespace std; // constexpr int MAX = 400; constexpr int MAX = 2601; 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/幅優先探索 // 迷路を幅優先探索する. // ※bfsの動作確認用. // @param s: 探索開始地点の迷路上の座標. // @return: 特に無し. void bfs(int s){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int v = q.front(); q.pop(); // 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); } } return; } int main() { // 1. 入力情報取得. cin >> R >> C >> sy >> sx >> gy >> gx; sy--, sx--, gy--, gx--; for(int i = 0; i < R; ++i){ string s; cin >> s; for(int j = 0; j < C; ++j){ board[i * C + j] = s[j]; } } // 2. 探索を開始し, 探索距離を更新. 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; 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 |
[入力例] 7 8 2 2 4 5 ######## #......# #.###### #..#...# #..##..# ##.....# ######## [出力例(debug版)] 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 0 0 1 0 0 0 0 0 0 0 2 3 0 11 10 11 0 0 3 4 0 0 9 10 0 0 0 5 6 7 8 9 0 0 0 0 0 0 0 0 0 11 ※AtCoderテストケースより [入力例] 5 8 2 2 2 4 ######## #.#....# #.###..# #......# ######## [出力例(debug版)] 0 0 0 0 0 0 0 0 0 0 0 10 9 8 9 0 0 1 0 0 0 7 8 0 0 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 10 ※AtCoderテストケースより [入力例] 16 12 1 1 15 11 ..########## #.##......## #.##.#.##.## #....#....## ##.######### ##..######## ###.######## ###......### ###.####..## ###.##.....# ###.####.#.# ###.##.#.#.# ###.####.#.# ###.###..### ###.#..#...# ###......### [出力例(debug版)] 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 9 10 11 12 13 14 0 0 0 3 0 0 8 0 12 0 0 15 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 12 13 14 15 0 0 0 0 0 0 11 0 0 0 0 16 17 0 0 0 0 0 12 0 0 19 18 17 18 19 0 0 0 0 13 0 0 0 0 18 0 20 0 0 0 0 14 0 0 0 0 19 0 21 0 0 0 0 15 0 0 0 0 20 0 22 0 0 0 0 16 0 0 0 22 21 0 0 0 0 0 0 17 0 21 22 0 22 23 24 0 0 0 0 18 19 20 21 22 23 0 0 0 24 |
■参照サイト
AtCoder Typical Contest 002