atcoder 九州大学プログラミングコンテスト2018 C - Ito Campus
普通の最短経路問題はBFSを1つだけ使うのだが、この問題は2つ使った。
なお、イノシシがゴールにたどり着かなければゴールできると勘違いしていたため、解くのに時間がかかってしまった。
コードはpythonで制限時間内に解くのは難しかったため、c++。
※10/24追記
pythonで解いてみた。
フィールドが大きいため、いつも通り書いてたら制限時間をオーバーしてしまう。そのため、いくつか工夫が必要。
①"迷路の外側1マスは壁で囲われている"と制約があるので、上下左右に移動しても外側で壁にぶつかるので、迷路からはみ出る処理はいらない。
②入力された迷路の2次元配列をそのまま利用し、移動したら'#'で上書きする。
③イノシシはまとめてdequeに格納して、BFSで処理する。