移動Bの回数を出来るだけ少なくしたいため、基本的な戦略は以下のようになります。

• 移動Aで移動可能な場所まで移動し、ゴールにたどり着けないのであれば、移動Bを用いて、移動Aだけでは移動出来ない場所に移動する

以上のように移動することを考えると、移動Bを使う回数が \(0\) 回で行ける領域、 \(1\) 回で行ける領域……と、移動Bを使う回数ごとに領域が分かれることがわかります。

これを実装するには、幅優先探索を使った実装が簡単です。以下、移動Bを使った回数を「コスト」と表現します。

まず、スタート地点から幅優先探索を用いて、新しくコスト \(0\) で辿り着けるマスを列挙します。次に、コスト \(0\) で辿り着けるマスから、移動Bで辿り着け、まだコスト \(0\) 以下でたどり着けないマスを列挙します。 次に、以上の操作で発見した、コスト \(1\) で辿り着けるマスたちをスタートとし、コスト \(1\) で辿り着ける全てのマスを、幅優先探索を用いて列挙します。これを繰り返すことで、全ての到達可能なマスに対して、到達するために必要なコストを求めることが出来ます。

また、移動におけるコストが \(0\) と \(1\) だけの場合は、01-BFSと呼ばれる実装が可能となります。 dequeを使用し、コストが \(0\) の移動先の頂点はdequeの先頭に、コストが \(1\) の移動先の頂点はdequeの末尾に追加することで、距離順に探索をすることが可能となります。

ただし、コスト \(1\) で追加された頂点がその後コスト \(0\) の移動のみで追加された際、\(2\) 回同じ頂点が追加されることになるため、その点の実装に注意してください。

計算量は、各マスについて\(25\) マスの移動しか調べないため、\(O(HW)\) となります。

実装例(TODO)