第8回日本情報オリンピック 予選4:薄氷渡り
問題
https://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/2009-yo-t4/2009-yo-t4.html
制約
考え方
始点を全探索する。始点から再帰的に進めるだけ進み、進んだ数の最大値で解を更新すれば良い。
どこに着目して考察するべきだったか
考え方の通り
何がバグっていたか
再帰から抜けるときに、条件をもとに戻すことを忘れた。再帰関数は以下のように実装したが、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); }
Submission #3674340 - 第8回日本情報オリンピック 予選(オンライン)
得た知見
再帰から戻るときにもとに戻すことを忘れない。(場合によりけりですが)