C++の練習を兼ねて, AtCoder Beginner Contest 213 の 問題E (Stronger Takahashi) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説および(複数の)正答者のプログラムを参考にして, AC版に到達できたと思う.
2. 01-BFSについて復習出来たので, 非常に良かったと思う.
3. 但し, 01-BFSは, いまいち, 本質を理解出来てないように見えるので, 引き続き, 今後の課題だと思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 213 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// ※※※ 解答不能 ※※※ // https://atcoder.jp/contests/abc213/editorial/2397 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; 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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front #define a first #define b second const int INF = 2020202020; constexpr int MAX = 252525; int board[MAX]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[505]; scanf("%s", c); rep(j, W) if(c[j] == '#') board[i * W + j] = 1; } // 2. 01-BFS(解説 および 複数の正答者プログラム参照). // https://ja.wikipedia.org/wiki/幅優先探索 // https://betrue12.hateblo.jp/entry/2018/12/08/000020 auto bfs01 = [&](int s, int* d){ // 2-1. 空のキュー. deque<P> dq; // 2-2. キュー に 保存. // -> キューに, 座標のみ保存だと, 正しく動作しない模様, // 正答者のプログラムをいくつか見たところ, 距離も合わせて保存する必要があるらしい. // dijkstra法 に, やや近い実装方法になると思われる. dq.pub({s, 0}); while(!dq.empty()){ // 2-3. キュー の 先頭要素を取り出す. // x: 列方向, y: 行方向 で考える. P u = dq.front(); int cx = u.a % W , cy = u.a / W; int dCur = u.b; dq.pof(); // 2-4. 最短距離更新. if(dCur >= d[u.a]) continue; d[u.a] = dCur; // 2-5. 周辺のマス を 確認. // -> 解説にある図で, * に 対する操作. // ※※※ 但し, * の マスへの 移動コストが, すべて 1 になる訳ではないので要注意. ※※※ // .***. // ***** // **T** // ***** // .***. // for(auto &x : {-2, -1, 0, 1, 2}){ for(auto &y : {-2, -1, 0, 1, 2}){ // 移動先候補のマス. int nx = cx + x; int ny = cy + y; int n = nx + ny * W; // 到達不可能なマスであれば, Skip. if(nx < 0 || nx >= W || ny < 0 || ny >= H || abs(x) + abs(y) == 4) continue; // 上下左右のマスで, '.' の場合は, コスト 0 の 移動, それ以外のマスは, コスト 1 の 移動と見る. if(!board[n] && x * y == 0 && abs(x + y) == 1) dq.puf({n, dCur + 0}); else dq.pub({n, dCur + 1}); } } } }; int d[MAX]; rep(i, MAX) d[i] = INF; bfs01(0, d); // 3. 出力. printf("%d", d[H * W - 1]); 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 |
[入力例] 5 5 ..#.. #.#.# ##.## #.#.# ..#.. [出力例] 1 ※AtCoderのテストケースより [入力例] 5 7 ....... ######. ....... .###### ....... [出力例] 0 ※AtCoderのテストケースより [入力例] 8 8 .####### ######## ######## ######## ######## ######## ######## #######. [出力例] 5 ※AtCoderのテストケースより [入力例] 2 12 .########### ###########. [出力例] 5 [入力例] 11 50 .################################################# ####.####....####....###....##..###....##.....#### ###.#.###.###.##..#########.###.######.##.######## ###.#.###.###.##.##########.###.######.##.######## ###.#.###.##.###.##########.###.######.##.######## ##.....##....###.#######....###.###....##.....#### ##.###.##.##.###.#######.######.######.##.######## ##.###.##.###.##.#######.######.######.##.######## ##.###.##.###.##..######.######.######.##.######## ##.###.##....####....###....##...##....##.....#### #################################################. [出力例] 12 |