C++の練習を兼ねて, AtCoder Beginner Contest 176 の 問題D (Wizard in Maze) を解いてみた.
■感想.
1. ゴリゴリ実装する羽目になってしまったものの, 久しぶりに解説見ずに, AC版を取れたので良かったと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 176 解説をご覧下さい.
■C++版プログラム(問題D／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 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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second #define pb push_back // constexpr int MAX = 1010; constexpr int MAX = 1010101; constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int board[MAX]; // 迷路情報. int connection[MAX]; // 連結成分番号を保存. int d[MAX]; // 開始頂点 からの 距離 を 保存. // https://ja.wikipedia.org/wiki/幅優先探索 // 迷路を幅優先探索する. // ※bfsの動作確認用. // @param s: 探索開始地点の迷路上の座標. // @param H: 行数. // @param W: 列数. // @param l: 連結成分番号(※1以上). // @return: 特に無し. void bfs(int s, int H, int W, int l){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. connection[s] = l; // 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 % W , cy = v / W; rep(i, 4){ nx = cx + dx[i]; ny = cy + dy[i]; n = nx + ny * W; // printf("cx=%d nx=%d cy=%d ny=%d\n", cx, nx, cy, ny); // 6. 訪問不可能なマス であれば, 処理をスキップ. if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue; if(board[n]) continue; // 7. 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 連結成分を設定. if(!board[n] && !connection[n]) connection[n] = l, q.push(n); } } return; } // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param d: 探索開始地点からの距離. // @return: 特に無し. void bfs(vvi &G, int s, int* d){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. d[s] = 0; // スタート地点は, 距離ゼロを指定. // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e]) continue; if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main() { // 1. 入力情報取得. int H, W, sh, sw, gh, gw; scanf("%d %d %d %d %d %d", &H, &W, &sh, &sw, &gh, &gw); sh--, sw--, gh--, gw--; rep(i, H){ char c[1010]; scanf("%s", c); int l = strlen(c); rep(j, W) if(c[j] == '#') board[i * W + j] = 1; } // rep(i, H){ // rep(j, W) printf("%d", board[i * W + j]); // puts(""); // } // 2. 探索を行い, 連結成分に分割. int idx = 0; rep(i, H){ rep(j, W){ int cur = i * W + j; if(!connection[cur] && !board[cur]) bfs(cur, H, W, ++idx); } } // rep(i, H){ // rep(j, W) printf("%d", connection[i * W + j]); // puts(""); // } // 3. 開始地点, ゴール地点の連結成分番号. int cs = connection[sh * W + sw]; int cg = connection[gh * W + gw]; // 4. ワープを使って移動できるか判定. set<P> s; rep(i, H){ rep(j, W){ int cur = i * W + j; // 現在位置. if(!board[cur]){ int u = max(i - 2, 0); // 最上行. int d = min(i + 2, H - 1); // 最下行. int l = max(j - 2, 0); // 最左列. int r = min(j + 2, W - 1); // 最右列. repx(h, u, d + 1){ repx(w, l, r + 1){ int nex = h * W + w; if(cur != nex && !board[nex]){ int cc = connection[cur]; // 現在位置の連結成分番号. int cn = connection[nex]; // 移動先の連結成分番号. if(cc == cn) continue; // 同じだったら次へ. if(cc > cn) swap(cc, cn); // 大小入れ替え. s.insert({cc - 1, cn - 1}); // グラフの頂点情報を登録. } } } } } } // for(auto &p : s) printf("%d %d\n", p.a, p.b); // 5. グラフ作成. vvi G(idx); for(auto &p : s){ G[p.a].pb(p.b); G[p.b].pb(p.a); } // 6. 開始地点 から 各頂点 までの距離を計算. bfs(G, cs - 1, d); // rep(i, H){ // rep(j, W) printf("%d", d[i * W + j]); // puts(""); // } // 7. 出力. int ans = -1; if(cs == cg) ans = 0; if(cs != cg && d[cg - 1]) ans = d[cg - 1]; printf("%d\n", ans); 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 137 138 139 140 141 142 143 144 145 146 147 |
[入力例] 4 4 1 1 4 4 ..#. ..#. .#.. .#.. [出力例] 1 ※AtCoderテストケースより [入力例] 4 4 1 4 4 1 .##. #### #### .##. [出力例] -1 ※AtCoderテストケースより [入力例] 4 4 2 2 3 3 .... .... .... .... [出力例] 0 ※AtCoderテストケースより [入力例] 4 5 1 2 2 5 #.### ####. #..## #..## [出力例] 2 ※AtCoderテストケースより [入力例] 12 10 1 1 12 10 .######### .######### ########## #.######## #..####### ##..#.#### ########## #####.#### #####..### ######..## ########## #########. [出力例] 3 [入力例] 5 5 1 1 5 3 .#.#. ##### ##### ###.# ##.## [出力例] -1 [入力例] 17 15 3 5 13 12 ####.#.#.###### ############### ####.#####.#### ############### ###########.### ########.###### #######...##### ########.###### #######.####### ######...###### #######.##.#### ############### ###########.### ##########...## ###########.### ############### ############### [出力例] 8 [入力例] 30 50 1 1 30 50 .################################################# ################################################## ##.############################################### ################################################## ####.############################################# ################################################## ######.###.###.################################### ################################################## ########.###.##################################### ################################################## ##########.####################################### ################################################## ########.###.##################################### ################################################## ######.###.###.################################### ################################################## ################.################################# ################################################## ##################.############################### ################################################## ####################.############################# ################################################## ######################.########################### ######################################.#####.##### ########################.#######.###.############# ##############################################.### ##########################.###.###.###.########### #################################.#.########.###.# ############################.###########.######### ##############################.#.#.##.####.###.##. [出力例] 25 |
■参照サイト
AtCoder Beginner Contest 176