ABC246 E - Bishop 2 - 01でもdijkstraでもないただのBFSで突破する
問題概要: 指定したマスに置かれているナイト（角行）がポーン（障害物）のある盤面を動いて指定したマスに移動するまでに最小何回動かせばよいですか？
提出 (本番AC, 148ms):
atcoder.jp
提出 (本番後, 104ms):
atcoder.jp
まず、本筋にはあまり関係ないですが、スタートとゴールのパリティが一致している必要があります（サンプルの2とかはこれで弾かれます）。盤面を探索すれば分かることなので、する必要はないですが、こういった考察が重要な問題もあったりしますよね。
01bfsでも拡張ダイクストラでも必要なように、「どの方向から来たか？」というのは重要です。簡単な観察として、駒は常に90度曲がり続けるのが最適です。これと、一度に同じ方向のマスを順番に見ていくことで、各マスに対して「この回数で行けたんやけど最短と違う？」の質問を飛ばす回数を減らすことができます。しかし、いい感じに探索方法を構成することで、「いまどの方向から来たか」だけを記憶しておくだけで、各マスに最短回数で行けるときの方向を記憶する必要がなくなります。詳しくは後述します。
BFSとして記憶しておく（キューに突っ込む）のは、「(x,y)座標に方向dから来た」という情報です。このマスからの探索は、dと90度曲がる方向のマスを近い順に見ていきます。まず、枠外にはみ出したらアウトです。障害物にぶつかるのもアウト、その先には進めません。dは実はこの探索方向を決めるのに使うだけで済みます。
次に、そのマスが未探索であれば、操作回数を記録してキューに突っ込みます。単純な考察として、BFSをしているので操作回数が小さい順に記録されていくので、後からの操作で操作回数が更新されることはないですが、ダイクストラを意識するのであれば、操作回数を比較するのもよいでしょう。
それで、最重要ポイントなんですが、見ていったマスの操作回数が現在の操作回数「より少ない」とき、ここで探索を打ち止めてよいです。まず、考察として、「既に操作回数が記録されているマスを見たとき、そのマスは現在見ている方向と90度曲がった方向から来ている」があります。そうでないと仮定すると、現在と同じ方向か180度曲がった方向から来た、ということになりますが前者は現在と同じ探索をしているので矛盾、後者であれば現在の探索の開始地点は既にその方向から探索されていなければおかしいので矛盾します。それで、現在の操作回数より少ない回数でそのマスに到達できたということは、そこから曲がることで現在の探索の操作回数以下の回数で探索することが可能です。
落とし穴ポイントは、現在の操作回数と同じときどうするか？です。これはキューに突っ込みはしないが、探索は続ける、のが正解です。そのマスから曲がるよりも少ない回数の操作回数で探索ができるからです。これを誤ってうちやめにすると奥に探索できていないマスが取り残されてしまいます（実際にやった）。
以上の探索方法によって、各マスについて探索されるのは直交する2方向の高々2回で済み、単純な01bfsよりも定数倍速くなりそうです。本番ではきちんと論理を詰めれず当てずっぽうに高速化を図っていっぱいTLEやWAを生んで無事死亡しましたが、高速化できて嬉しいですね。雑な解説ですが、なにかの役に立てば幸いです。
