解法
1ターンに1マスの移動であればグリッド上のBFSで解けますが、今回は1ターンに マスまで動くことができます。これをそのままBFSで処理すると1つのマスから遷移可能なマスが最大
個になり、全体計算量
になって間に合いません。
具体的にどのように無駄が生じているのかを、マスが一直線に並んでいるケースで見てみます。マス内の数値はスタートからの最短距離です。
このように、同じターン数で自分より先を行っている経路を後から追うのは無駄です。これを除外するため、BFSに以下のような改良を加えます。
- スタートからマス
までの距離を
として、キュー等を用いたBFSを行う。
- あるマス
からの遷移として、4方向の移動をそれぞれ試す。決めた方向に対して、
マス移動した先を順番に見ていく。
- このとき移動先のマス
が、障害物、枠外、または
であるようなマスだった場合、その方向の遷移をそこで打ち切る。
- その上で、
が未訪問マスであった場合は
としてキューに入れる。
- このとき移動先のマス
このようにすると、先ほどの無駄な移動は打ち切られます。
この解法の正当性確認と計算量評価をしましょう。正当性は、「 であった場合、打ち切らずに
からの遷移を考える代わりに、
からの遷移をすることでより良い遷移ができる」ことから言えます。より良い遷移とは具体的には、より遠くのマスまで届いてかつ
の値が同じかより小さい、という意味です。
計算量については、あるマスに対して遷移で入ってくる回数を考えると分かります。入ってくるけどそこで打ち切られるような場合を除くと、あるマスに入ってくる回数は各方向あたり高々1回ずつです。具体的にはそのマスにある方向から流入可能なマスのうち、 が最も小さく、かつ
が同じものの中では最も近いものからしか流入しません。
よって、方向数 を定数と見なせば「打ち切られ」以外の遷移回数は合計で
。打ち切られる回数の合計も(今度は遷移元に注目すると)マス数×方向数で
です。よって全体計算量
となり間に合います。