C++の練習を兼ねて, 競プロ典型 90 問 の 問題043 (Maze Challenge with Lack of Sleep) を解いてみた.
■感想.
1. 問題043は, 01-BFS, ダイクストラ法の方針で, いくつか実装したものの, どれもAC版に到達できなかったので, 解説プログラムに, 一部手を加えた版(※)を提出して, ようやく, AC版に到達出来た.
※解説プログラムでは, 二次元座標で実装されているようです.
2. 問題自体は, 個人的には, 非常に面白く, さらに, 曲がった回数の情報をどのように管理するか(問題043 解説), について, 全く発想に出てこない概念だったので, 非常に勉強になったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題043 を ご覧下さい.
■C++版プログラム(問題043／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 |
// 解答不能. // https://github.com/E869120/kyopro_educational_90/blob/main/sol/043.cpp // 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 a first #define b second #define pof pop_front #define pob pop_back #define pub push_back #define puf push_front constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; const int INF = 2020202020; int board[1010][1010]; int d[1010101][4]; // 上下左右の4方向を記録. int main() { // 1. 入力情報. int H, W, rs, cs, rt, ct; scanf("%d %d %d %d %d %d", &H, &W, &rs, &cs, &rt, &ct); rs--, cs--, rt--, ct--; rep(i, H){ char c[1010]; scanf("%s", c); rep(j, W) if(c[j] == '.') board[i][j] = 1; } // 2. 01-BFS(解説プログラムを一部修正). // 左 … 0, 上 … 1, 右 … 2, 下 … 3. auto bfs01 = [&](int s){ // 2-1. 空のキュー. deque<P> dq; // {座標, 方向}. // 2-2. 探索開始地点 s をキュー に追加. rep(i, 4) d[s][i] = 0, dq.pub({s, i}); // 2-3. キューが空になるまで繰り返し. while(!dq.empty()){ // 2-4. キュー の 先頭要素を取り出す. P c = dq.front(); dq.pof(); // 2-5. 取り出した要素を処理. // x: 列方向, y: 行方向 で考える. int nx, ny, n, nc; int cx = c.a % W , cy = c.a / W; rep(i, 4){ // 2-6. 訪問先の候補となるマスについて情報を取得. nx = cx + dx[i]; ny = cy + dy[i]; n = nx + ny * W; nc = d[c.a][c.b] + (c.b != i ? 1 : 0); // 2-7. 訪問不可能なマスは, 処理をスキップ. if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue; if(!board[ny][nx]) continue; // 2-8. よりコストが少ないマスは, 処理をスキップ. if(d[n][i] <= nc) continue; // 2-9. キューに追加. d[n][i] = nc; if(i != c.b) dq.pub({n, i}); else dq.puf({n, i}); } } return; }; rep(i, 1010101) rep(j, 4) d[i][j] = INF; bfs01(rs * W + cs); // 3. 出力. int ans = INF; rep(i, 4) ans = min(ans, d[rt * W + ct][i]); printf("%d", 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 |
[入力例] 3 3 1 1 3 3 ..# #.# #.. [出力例] 2 ※AtCoderテストケースより [入力例] 3 3 2 1 2 3 #.# ... #.# [出力例] 0 ※AtCoderテストケースより [入力例] 4 6 2 1 1 5 ...#.. .#.##. .#.... ...##. [出力例] 5 ※AtCoderテストケースより [入力例] 4 7 1 2 4 2 #...... ..####. .#####. ....... [出力例] 2 ※解説上のテストケースより [入力例] 8 11 4 3 8 10 ........... .#.###..#.. .#......#.. ...##..#... .....#.#..# #..#....... .#...#.#.#. #..#...#... [出力例] 5 [入力例] 12 17 2 3 11 15 ......#.#..#..#.. .#.#..#.........# .#.#..#..#..#.#.. ....#.#.#..#....# ..#.#.........#.. #...#.#.#.#.#.#.# ..#.....#.#.#.#.# #...#.#.#....#... ......#....##.#.# ..#...#..#..#.... ....#.#.#....#.#. ......#....#..... [出力例] 8 |