SRM368 Div2 900

問題

長方形のボードの各セルに数字またはHが書いてある。
このボードを使ってゲームをする。ゲームのルールは、左上のセルにトークンを置いたところから始めるものとして、「今トークンがいる場所の数字の分だけ上下左右に動く」ことを繰り返す。
ボードの外にでるか、穴を示すHと書いてあるセルについたらゲームは終了となる。
できるだけ長くボードの上で動いていたい。この時、最大で何回動くことができるか。
もし、無限に動ける場合は-1を返す。

考え方

メモ化dfs。メモは、「もう訪れたセルかどうかvisited」と「そのセルに最大何回動いて訪れたかmaxmove」。
dfs(int x, int y, int move)として、その地点から動けるだけ各方向に動く。
枝狩りは、そのセルに過去move以上で訪れていた場合と無限ループする場合。
visitedのメモは、ルートが各状態で独立なので、dfsの初めでvisited[y][x]をtrueにしたら、dfsの最後でvisited[y][x]はfalseに直す。

ちなみに、bfsでやると、各状態にvisitedのフラグを持たせないといけないのでメモリが足りない。