C++の練習を兼ねて, AtCoder Beginner Contest 151 の 問題D (D – Maze Master) を解いてみた.
■感想.
1. 幅優先探索の復習が出来たので良かったと思う.
2. 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 151解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #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--) constexpr int MAX = 625; constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int H, W; 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初期化. memset(memo, 0, sizeof(memo)); // 3. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 4. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 5. キューから取り出す. int v = q.front(); q.pop(); // 6. 取り出した要素を処理. // 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; // 7. 訪問不可能なマス であれば, 処理をスキップ. if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue; if(board[n] == '#') continue; // 8. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定. if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n); } } return; } int main(){ // 1. 入力情報. scanf("%d %d", &H, &W); rep(i, H){ char c[33]; scanf("%s", c); rep(j, W) board[i * W + j] = c[j]; } // 2. スタートとゴールを決めて, 移動回数の最大値を探索. int ans = 0; rep(si, H){ rep(sj, W){ if(board[si * W + sj] != '#'){ bfs(si * W + sj); rep(gi, H) rep(gj, W) ans = max(ans, memo[gi * W + gj]); } } } // 3. 出力. 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 |
[入力例] 3 3 ... ... ... [出力例] 4 ※AtCoderテストケースより [入力例] 3 5 ...#. .#.#. .#... [出力例] 10 ※AtCoderテストケースより [入力例] 1 1 . [出力例] 0 [入力例] 10 10 #.....#... ..#..#..#. .#..#..#.. #..#..#..# ..#..#..#. .#..#..#.# ...#..#... ..#..#..#. .#..#..#.. #.#...#.## [出力例] 56 [入力例] 20 20 ...###....#.#...###. .#.#....#...##..#.#. ...#...##.####....#. ...###..#...##..#... .#.#...##.#.##.###.. ...###..#...##..##.. .#.#....##.###..#... ...#...##...###.##.. ...#..##.##.##..##.. ...#....#...##..###. .#.###..#...##.###.. ...#....#.#.##..##.. .#.#...##.#..#..###. ...#.#..#....#...#.. .#.#....#.#.#..####. ...#..###...#...##.. ...#....#.#.##..##.# .#.#....#...#..###.# ...#....#.#.##..##.# #.......#......###.. [出力例] 116 |
■参照サイト
AtCoder Beginner Contest 151