解説
この問題は、DFSで経路を列挙することで解くことができます。
DFSについては、けんちょんさんの記事を参照してください。
経路の総数が20万通りを超えないことが問題文で保証されているので、適当にDFSをして経路を列挙し、その中で最も長いものの長さを出力すれば良いです。
DFSでは、遷移前の状態の次に、そこから遷移したあとの状態をすぐに探索します。 よって、どのマスを既に通ったかを保存し、進む先のマスに印をつけたあと先を探索して、戻ってきたら印を外す、とすれば簡単に探索できます。
このように、DFSで再帰関数などの外部に状態を持って、探索が終わったら状態を戻す、というテクニックはよく使われます。 覚えておきましょう。
