問題

https://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/2009-yo-t4/2009-yo-t4.html

制約

$1 \le m \le 90$
$1 \le n \le 90$

考え方

始点を全探索する。始点から再帰的に進めるだけ進み、進んだ数の最大値で解を更新すれば良い。

どこに着目して考察するべきだったか

考え方の通り

何がバグっていたか

再帰から抜けるときに、条件をもとに戻すことを忘れた。再帰関数は以下のように実装したが、visited[nh][nw] = false; が必要。

       void dfs(int nh, int nw, int count, boolean[][] visited) {

            visited[nh][nw] = true;

            for (int i = 0; i < 4; i++) {
                int mh = nh + mh4[i];
                int mw = nw + mw4[i];
                if (isInside(mh, mw) && !visited[mh][mw] && exists[mh][mw]) {
                    dfs(mh, mw, count+1, visited);
                }
            }

            visited[nh][nw] = false;

            ans = Math.max(ans, count);

        }