ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

九州大学プログラミングコンテスト2018 C - Ito Campus

問題
提出コード

解法

何も考えずにうしくんのゴールへの行き方をBFSで求めようとすると、マス目を移動するたびに安全なマスかどうか調べるため、時間内に解くことができません。
しかし、この問題ではイノシシが移動することはないため、安全なマスであるかどうかは、入力が与えられた時点で確定しています。
イノシシがX回以内の移動でたどり着くことができるマスは全て安全でないマスになるので、それを最初に調べてしまい、壁にしておくことで、あとはうしくんのゴールへの最小手数をBFSで求めるだけで答えが求まります。
ということで、最初にイノシシがいるマスからBFSを行うのですが、このとき、それぞれのイノシシについてBFSをするのではなく、全てのイノシシについて同時にBFSをする必要があります。
最終的に、2回のBFSをすることで、この問題を解くことができます。

感想

最初に問題を読んだとき、それぞれのイノシシについてBFSするだけ、と思ったのですが、それだと計算が間に合わないということに気づいたので、少し悩みました。
バグもほぼなく通せたので良かったです。