C++の練習を兼ねて, 競プロ典型 90 問 の 問題072 (Loop Railway Plan) を解いてみた.
■感想.
1. 問題072は, 実装方針が見えなかったので, (問題072 (Loop Railway Plan) 解説プログラム) を参考に実装したところ, AC版に到達出来た.
2. 深さ優先探索(応用版, Backtracking) の 復習 が出来たので, 非常に, 良かったと思う.
但し, Backtracking について, 本質的な部分が, 理解できてないため, 引き続き, 今後の課題になると思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題072 を ご覧下さい.
■C++版プログラム(問題072／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 |
// 解答不能. // https://github.com/E869120/kyopro_educational_90/blob/main/sol/072.cpp // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; #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 pb push_back constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); vs board; rep(i, H){ char c[22]; scanf("%s", c); string s(c); board.pb(s); } // 2. dfs(Backtracking). // https://ja.wikipedia.org/wiki/深さ優先探索 int ans = -1; bool memo[20][20]; rep(i, 20) rep(j, 20) memo[i][j] = false; auto dfs = [&](auto&& self, int sx, int sy, int px, int py) -> int{ // 2-1. 終了条件. if(sx == px && sy == py && memo[px][py]) return 0; // 2-2. 訪問したことを記録. memo[px][py] = true; // 2-3. dfs. // -> ret の 初期値は, どのくらい小さくするかは, よく理解出来てない. int ret = -111; rep(i, 4){ // 隣接マスを用意. int nx = px + dx[i]; int ny = py + dy[i]; // 隣接マスが, 到達不可能な場合(山とか). if(nx < 0 || ny < 0 || nx >= H || ny >= W || board[nx][ny] == '#') continue; // 隣接マスが, 開始頂点でないが, 訪問済みの場合. if((sx != nx || sy != ny) && memo[nx][ny]) continue; // 移動したマス数を取得. int v = self(self, sx, sy, nx, ny); // 最大値更新. ret = max(ret, v + 1); } // 2-4. 訪問してない状態に戻す. memo[px][py] = false; // 2-5. 処理終了. return ret; }; // 3. 全探索. rep(x, H) rep(y, W) ans = max(ans, dfs(dfs, x, y, x, y)); // 4. 鉄道路線が通るマスの数が, 3マス以下の場合(鉄道路線が無い場合). if(ans <= 3) ans = -1; // 5. 出力. 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 ... .#. ... [出力例] 8 ※AtCoderテストケースより [入力例] 1 6 ...... [出力例] -1 ※AtCoderテストケースより [入力例] 4 4 .... #... .... ...# [出力例] 12 ※AtCoderテストケースより [入力例] 5 5 ..... .#... ..... ...#. .#... [出力例] 20 ※整数 H, W が, 問題文の制約条件から範囲外であるケース. -> 以下のような経路で, 20 と 分かる. @@@@@ @#@@@ @.@@@ @@@#@ .#@@@ [入力例] 6 6 .....# .#.... ...... ...#.# .#.... ...... [出力例] 30 ※整数 H, W が, 問題文の制約条件から範囲外であるケース. -> 以下のような経路で, 30 と 分かる. @@@@@# @#@@@@ @@@.@@ @@@#@# @#@@@@ @@@@@@ |
■参照サイト
072 – Loop Railway Plan
問題072 (Loop Railway Plan) 解説
問題072 (Loop Railway Plan) 解説プログラム
