2011JOI予選5 チーズ 解説

問題リンク

解説

ねずみは、硬さの小さい順にチーズを食べていくので、あるチーズを食べたあと、次のチーズがある場所への最短経路がわかれば、これらの経路をつなげたものが答えとなります。 このような二次元のグリッド上で最短経路問題を解くには、BFS（幅優先探索）が有効です。

このような問題は、予選を突破するためにはすらすら（20分以内には）解ける必要があるでしょう。 簡単な最短経路問題に適用できるアルゴリズムは限られているので、この記事を参考にして、最短経路問題をスパッと解けるようにしましょう。