2009JOI予選4 薄氷渡り 解説

問題リンク

解説

この問題は、DFSで経路を列挙することで解くことができます。

DFSについては、けんちょんさんの記事を参照してください。

経路の総数が20万通りを超えないことが問題文で保証されているので、適当にDFSをして経路を列挙し、その中で最も長いものの長さを出力すれば良いです。

DFSでは、遷移前の状態の次に、そこから遷移したあとの状態をすぐに探索します。 よって、どのマスを既に通ったかを保存し、進む先のマスに印をつけたあと先を探索して、戻ってきたら印を外す、とすれば簡単に探索できます。

このように、DFSで再帰関数などの外部に状態を持って、探索が終わったら状態を戻す、というテクニックはよく使われます。 覚えておきましょう。