トヨタ自動車 AtCoder Beginner Contest 348 に参加した感想の続き（4問目）です。
問題の内容
H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマス目を (i,j) と表します。各マスの状態は文字 A_ij で表され、意味は以下の通りです。
. : 空きマス。
# : 障害物。
S : 空きマスかつスタート地点。
T : 空きマスかつゴール地点。今いるマスから上下左右に隣り合う空きマスへ移動することができますが、そのときはエネルギー 1 を消費します。エネルギーが 0 の状態では移動できません。またグリッドの外へ移動することもできません。
グリッドには合計で N 個の薬があります。i 番目の薬は空きマス (R_i ,C_i) にあり、使うとエネルギーを E_i にすることができます。現在のエネルギーが E_i に変更されるのであって必ずしもエネルギーが増えるとは限らないことに注意してください。自分のいるマスに薬がある場合、使うこともできるし使わないこともできます。使った薬は当然のことながらなくなります。
高橋くんが最初はエネルギー 0 の状態でスタート地点にいます。上記の条件下でゴール地点まで移動できるかどうか判定してください。
入力
H W （1 ≦ H, W ≦ 200）
A_11 A_12 A_13 … A_1W
A_21 A_22 A_23 … A_2W
A_31 A_32 A_33 … A_3W
… …
A_H1 A_H2 A_H3 … A_HW
N （1 ≦ N ≦ 300）
R_1 C_1 E_1
R_2 C_2 E_2
R_3 C_3 E_3
… …
R_N C_N E_N
障害物がある迷路があってスタート地点からゴールまでいけるか？ そのときの最短経路は？という問題はよくあります。ゲームをつくっているとこういう問題と似たことをよく考えさせられます。
ちょっと特殊なのが「途中に落ちている薬を使ったら体力が回復する」のではなく「体力が強制的にその値になる」「薬は使ってもいいし使わなくてもよい」「体力が尽きたら動けなくなる ⇒ 失敗」という部分でしょうか？
鳩はこう考えて爆死した！
通れるところ、通れないところを表す二次元配列をつくる。
別の二次元配列をつくってそこに高橋くんのエネルギーを記録する。
薬は使ったらなくなるので存在するかどうかを表す二次元配列をつくる。
二次元配列がたくさんできてしまったが、あとは幅優先探索で実際に高橋くんを移動させてみる
壁や配列外、エネルギーがなくなったときは移動できない
最初はエネルギー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 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 |
using System; using System.Collections.Generic; using System.Linq; class Medicine { public Medicine(int row, int col, int energy) { Row = row; Col = col; Energy = energy; } public int Row; public int Col; public int Energy; } class Program { static void Main() { // 入力されたデータをSolverクラスのフィールド変数にセットする // Solverクラスを定義したのはMainメソッドがあるクラスのなかを // あまりゴチャゴチャさせたくなかったからで深い意味はありません int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } char[,] map = new char[H, W]; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) map[r, c] = vs[c]; } int N = int.Parse(Console.ReadLine()); List<Medicine> medicines = new List<Medicine>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); medicines.Add(new Medicine(vs[0] - 1, vs[1] - 1, vs[2])); } Solver solver = new Solver(H, W, map, medicines); // 必要なデータをすべて渡したのでSolverクラスのなかで処理を開始する solver.Solve(); } } class Solver { public int H, W; public char[,] Map = { { } }; public List<Medicine> Medicines = new List<Medicine>(); public int Srow, Scol, Trow, Tcol; public int[,] MedicineMap = { { } }; public Solver(int h, int w, char[,] map, List<Medicine> medicines) { // コンストラクタの引数をコピー H = h; W = w; Map = map; Medicines = medicines; // マップからスタート地点とゴールの座標を取得 for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) { if (Map[row, col] == 'S') { Srow = row; Scol = col; } if (Map[row, col] == 'T') { Trow = row; Tcol = col; } } } // 使用されていない薬をマップにセット MedicineMap = new int[H, W]; foreach (Medicine medicine in Medicines) MedicineMap[medicine.Row, medicine.Col] = medicine.Energy; } public void Solve() { // 高橋くんがマップ内で移動したときのエネルギーを保存する // エネルギーが0のときは移動できない int[,] energy = new int[H, W]; // スタート地点に薬があればエネルギーをセットする // 使われてしまった薬はなくなるので 0 をセットする energy[Srow, Scol] = MedicineMap[Srow, Scol]; MedicineMap[Srow, Scol] = 0; // スタート地点でエネルギーが 0 なら動けない "No" を出力して終わり if (energy[Srow, Scol] == 0) { Console.WriteLine("No"); return; } // 幅優先探索で移動できるところに移動する。これでゴールにたどり着けるか？ Queue<int> queueX = new Queue<int>(); Queue<int> queueY = new Queue<int>(); queueX.Enqueue(Scol); queueY.Enqueue(Srow); int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; bool clear = false; while (queueX.Count > 0) { int x = queueX.Dequeue(); int y = queueY.Dequeue(); for (int i = 0; i < 4; i++) { // マスの上下左右に移動できるが、配列の範囲外や壁であれば移動できない int newX = x + dx[i]; int newY = y + dy[i]; if (newX < 0 || newY < 0 || newX >= W || newY >= H) continue; if (Map[newY, newX] == '#') continue; // 移動するとエネルギーを 1 消費するので減らす // もし移動先に薬があって薬を使ったほうがいい場合はエネルギーを回復させる // 使った薬はなくなるので Medicines[newY, newX] には 0 を代入する energy[newY, newX] = energy[y, x] - 1; if (MedicineMap[newY, newX] > energy[newY, newX]) { energy[newY, newX] = MedicineMap[newY, newX]; MedicineMap[newY, newX] = 0; } // 移動先がゴールだった場合はエネルギー 0 でも成功 if (newX == Tcol && newY == Trow) { clear = true; break; } // 移動先でエネルギー 0 になったら動けないので失敗 // 次の選択肢としてはありえないのでキューには追加しない if (energy[newY, newX] <= 0) continue; // 上記以外は次の移動先の候補としてありえるのでキューに追加する queueX.Enqueue(newX); queueY.Enqueue(newY); } } // ゴールに到達することなくループを抜けた場合はゴールする方法は存在しない // ゴールに到達できるのであれば clear == true になっているので "Yes" を出力する if (clear) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
これでテストが通るのかというと以下の2つは通ります。
|
1 2 3 4 5 6 7 8 9 10 |
4 4 S... #..# #... ..#T 4 1 1 3 1 3 5 3 2 1 2 3 1 |
期待どおり ‘Yes’ と出力されます。
|
1 2 3 4 5 |
2 2 S. T. 1 1 2 4 |
これも期待どおり ‘No’ と出力されます。
しかし以下の場合、テストがとおりません。’Yes’ を期待しているのですが実行すると ‘No’ と出力されます。
|
1 2 3 4 5 6 7 8 9 |
4 5 ..#.. .S##. .##T. ..... 3 3 1 5 1 2 3 2 2 1 |
最短コースでゴールに向かおうとするとエネルギーが足りなくなるので、いったん逆方向に移動してそれから元きた道を戻って来るルートを通ることでゴールすることができる場合があります。ところが上記のコードでは元きた道を戻って来るあいだに別の探索がおこなわれて途中で必要な薬がなくなってしまっていて、実はゴールにたどり着けるのに “No” と出力される場合が多々あるのです。
公式の解説によるとこうです。
薬は使うとなくなります。そこで薬があるかどうかを表すフラグを定義しましたが、じつは考える必要はありません。薬を使うと強制的にエネルギーが一定の値にリセットされるので、何度でも使えるとしても問題ありません。その場合は最後に使った後の行動を代わりに初めて使った後にすればよいからです。
ただ上記のコードで薬に関するフラグをなしにしても問題は解決しません。無限ループのような状態になっていつまで経ってもプログラムが終わりません。
では、どうすればよいのでしょうか？
正しい解法
薬がエネルギーを増やすのではなく、エネルギーを強制的にその値にするものであるという性質のものである以上、ある薬を使った時点で高橋くんの位置と彼のエネルギーは一意です。
そこでこう考えます。
薬 i が置いてあるマスがあり、その薬をつかったあと別の薬 j がある場所へ移動する有向グラフを考えます。薬 i を使ったらエネルギーはそれまでのエネルギーとは無関係に固定の値に変化してしまうので、i から j へ移動可能か、j から i へ移動可能かがわかります。
あとは移動が可能な部分だけで有向グラフを構築して、その上で幅優先探索をすることでこの問題を解くことができます。この有向グラフは薬の位置だけでなくスタート地点とゴール地点も必要になりますが、ゴール地点に薬がない場合はダミーの薬をおくようにすると考えやすいと思います。またスタート地点が薬をおいている位置でない場合はそもそもゴールにはたどり着けません。
薬 i を使った後、他の薬を使わずに薬 j の位置にたどり着けるか？という問題は幅優先探索で求めればよいです。N 個の薬それぞれについて幅優先探索をするのであれば、計算量は O(HWN) です。H と W の最大値は 200, N の最大値は 300 であることから充分間に合います。また、これによって構築された有向グラフを探索する計算量はこれほど大きくはなりません。
薬と薬のあいだは移動可能か？
まず幅優先探索で n 番目から他の薬まで移動するコストを求めます。コストを初期化しなければなりませんが、最小になる値を求めるので int.MaxValue などの巨大な数や -1 などの不適切な数を使います。かつて深く考えないで int.MaxValue をつかってオーバーフローしてバグったことがあるのでここでは -1 をつかっています。グリッドの大きさから考えて1,000,000のような値になることはありえないのでオーバーフローを気にしなくてよいほどほどに大きな値を使うのもありだと思います。
幅優先探索が終わったら出発点のエネルギーと移動コストが同じか小さいのであれば移動可能です。移動可能な頂点番号をリストで返します。このとき出発点と終点が同じ場合は意味がないので結果から取り除きます。またこのとき移動コストが -1 だとそもそもたどり着けないことになるのですが、それを失念していてバグを連発してしまいました。やはりオーバーフローの心配がない大きな数で初期化したほうがよいみたいです。
|
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 |
class Solver { public List<int> BFS(int n) { Medicine start = Medicines[n]; int[,] costs = new int[H, W]; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) costs[row, col] = -1; } Queue<int> queueX = new Queue<int>(); Queue<int> queueY = new Queue<int>(); queueX.Enqueue(start.Col); queueY.Enqueue(start.Row); costs[start.Row, start.Col] = 0; int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; while (queueX.Count > 0) { int x = queueX.Dequeue(); int y = queueY.Dequeue(); int curCost = costs[y, x]; for (int i = 0; i < 4; i++) { // マスの上下左右に移動できるが、配列の範囲外や壁であれば移動できない int newX = x + dx[i]; int newY = y + dy[i]; if (newX < 0 || newY < 0 || newX >= W || newY >= H) continue; if (Map[newY, newX] == '#') continue; int nextCost = curCost + 1; if(costs[newY, newX] != -1 && costs[newY, newX] <= nextCost) continue; costs[newY, newX] = nextCost; queueX.Enqueue(newX); queueY.Enqueue(newY); } } List<int> rets = new List<int>(); for (int i = 0; i < Medicines.Count; i++) { if (i == n) continue; if(costs[Medicines[i].Row, Medicines[i].Col] == -1) continue; if (costs[Medicines[i].Row, Medicines[i].Col] <= Medicines[n].Energy) rets.Add(i); } return rets; } } |
相互に移動可能な薬で構築された有向グラフで s-t 間の移動は可能か？
BFS2メソッドは移動が可能な部分だけで有向グラフを構築し、出発点からゴールまで移動できるかその結果を返します。まず出発点には必ず薬がないと、移動を開始することすらできないので、falseを返します。
ではゴールはどう考えればよいでしょうか？ ゴールもダミーの薬があることにすると処理が簡単になります。テストケースによってはゴールにも薬があるものもあるかもしれませんが問題ありません。
あとは隣接リストをつくってそれぞれの薬の位置から別の薬の位置まで移動できるものを取得します。取得できた有向グラフで出発点からゴールまで移動できるでしょうか？
|
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 |
class Solver { bool BFS2() { // ゴールも薬があると考える Medicines.Add(new Medicine(Trow, Tcol, 1)); int count = Medicines.Count; // 隣接リストを作る List<int>[] nexts = new List<int>[count]; for (int i = 0; i < count; i++) nexts[i] = new List<int>(); for (int i = 0; i < count; i++) { foreach (int index in BFS(i)) nexts[i].Add(index); } // 有向グラフの出発点からゴールまで移動できるか調べる Queue<int> queue = new Queue<int>(); bool[] visits = new bool[count]; Medicine start = Medicines.FirstOrDefault(_ => _.Row == Srow && _.Col == Scol); Medicine goal = Medicines.FirstOrDefault(_ => _.Row == Trow && _.Col == Tcol); if (start != null) { int sIndex = Medicines.IndexOf(start); int tIndex = Medicines.IndexOf(goal); visits[sIndex] = true; queue.Enqueue(sIndex); while (queue.Count > 0) { int curIndex = queue.Dequeue(); foreach (int nextIndex in nexts[curIndex]) { if (visits[nextIndex]) continue; visits[nextIndex] = true; queue.Enqueue(nextIndex); if (nextIndex == tIndex) return true; } } return false; } else return false; } } |
