競プロ日記 2020年8月24日 Manuel1024

AtCoder Beginner Contest 176 D – Wizard in Maze を解いた記録

問題の概要

縦\(H\)マス，横\(W\)マスの迷路がある．上から\(i\)行目，左から\(j\)列目のマス\( (i, j) \)は，
\(S_{ij}\)が”#“のとき壁であり．”.“のとき道である．

マス\((C_h, C_w)\)からマス\((D_h, D_w)\)まで移動したい．移動方法は次の2つがあり，どちらも0回以上の任意の回数だけ使える．

どちらの移動方法でも，迷路の外へは移動できない．

マス\((C_h, C_w)\)からマス\((D_h, D_w)\)まで移動するときにワープ魔法を使用する回数の最小値を求めよ．
ただし，マス\((C_h, C_w)\)からマス\((D_h, D_w)\)までの移動が不可能な場合は \(-1\) を出力せよ．

始点のマスから何かしらの方法で到達可能なマスについて，ワープ魔法の使用回数の最小値を求めます．
到達可能なマスを調べるだけなら，伝家の宝刀†二分探索†…ではなく幅優先探索で次のようにすればOKです．

キュー\(Q\)と当該マスに訪問したか否かの情報を管理する配列を用意する．
\(Q\)に始点マスの情報を入れる．
\(Q\)が空になるまで，以下の操作を繰り返す．
1. キューからマスの情報を1つ取り出す．取り出したマスを\(cur\)とする．
2. \(cur\)が未訪問ならそのマスは訪問済みとして（配列に記録して）次のステップへ進む．訪問済みだった場合は何もせずに1.へ戻る．
3. \(cur\)に隣接している（上下左右にある）マスのうち，道であるものを全て\(Q\)に入れる．
4. \(cur\)からワープ魔法で到達できるマスのうち，道であるものを全て\(Q\)に入れる．
当該ノードに訪問したか否かの情報を管理する配列を見て，訪問済みとなっているマスが始点から到達可能なマスである．

しかしこの方法では，ワープ魔法を使用する回数の最小値が求まりません．
この方法では歩いていけば到達できるマスについてもワープ魔法で先に到達してしまう（ワープ魔法で訪問したという記録が残る）可能性があるためです．

そこで，上記の方法を以下のように改良します．（ダイクストラ法もどきか？）

優先度付きキュー\(Q\)，当該マスに訪問したか否かの情報を管理する配列，当該マスへ到達するとき際のワープ魔法の最小使用回数を記録する配列を用意する．
\(Q\)にはマスの番地とワープ魔法の使用回数の組を投入するものとし，\(Q\)からはワープ魔法の使用回数が少ないデータが先に取り出されるものとする．
\(Q\)に始点マスの情報を入れる．ワープ魔法の使用回数は0回とする．
\(Q\)が空になるまで，以下の操作を繰り返す．
1. \(Q\)からマスの情報を1つ取り出す．取り出したマスを\(cur\)とする．
2. \(cur\)が未訪問ならそのマスは訪問済みとして（訪問した情報とワープ魔法の最小使用回数を配列に記録して）次のステップへ進む．
  訪問済みだった場合は何もせずに1.へ戻る．
3. \(cur\)に隣接している（上下左右にある）マスのうち，道であるものを全て\(Q\)に入れる．ワープ魔法の使用回数は\(cur\)のそれと同一とする．
4. \(cur\)からワープ魔法で到達できるマスのうち，道であるものを全て\(Q\)に入れる．ワープ魔法の使用回数は\(cur\)のそれ+1回とする．
当該ノードに訪問したか否かの情報を管理する配列を見て，訪問済みとなっているマスが始点から到達可能なマスである．

このようにすれば，同じマスについてワープ魔法の使用回数が異なる到達方法がある場合でもワープ魔法の使用回数が最小のデータが一番最初に取り出されます．
各マスについてワープ魔法の最小使用回数を求められるようになったので，あとは実装するだけです．

ABC176では5完できたので（ABC171以来），前回に引き続き水パフォをとれました．レーティングも1100台に到達しました．ここまで来たら水コーダーを目指したいです．
それはそれとして彼女ほしいです．