Time-4 - DekoBoko Mountain

2 secs 1024 MB

この問題は 再帰的な探索 を問います。

選ぶマスは $HW$ 個存在するので、それぞれのマスから、移動先、ならびに移動元の数値を持たせて再帰的に探索していくことで正解できます。ここでは深さ優先探索(DFS)や幅優先探索(BFS)などの探索法を用いて実装できます。

$1$ つのマスあたり探索回数は最悪 $O(HW)$ かかるので、全体で $O(H^2W^2)$ で実装することができます。以下が解答例になります。

※ここでは探索法の説明は省略します。ご自身で調べてみてください。