■http://anond.hatelabo.jp/20081223190850

再帰するトコ，>= 0 じゃなくて > 0 じゃね？

「薄氷じゃないとこに乗ったとき」じゃなくて「東西南北どちらにも薄氷がなくなったとき」にresult記録行うべき．

んでもって result は最長のパス一個だけ持っておけば良いんでは．

あとはスタート地点候補全部について調べる必要あるかな．

大まかな方針としてはDFSによる全探索でOKと思われる．親切にも『移動方法は20万通りを超えない』ことが分かっているのだし．

すぐできる最適化としては

• すでに通ったかのチェックを O(1) でできるようにする
  • 例) visited[x][y] = True
• routeを連結リストで持つことによって，全コピーするのを防ぐ．
  • 例) route = ((x,y), route)
• てか長さだけ分かればいいんだからそもそも route を記録する必要ないよね

Permalink | 記事への反応(0) | 00:50

ツイートシェア