状態数は少なそうなので普通にDFSをすれば良さそう。
同じ状態にたどり着くケースはなくはない。
少し心配なのでメモ化してみる(2^20 * 19 * 15)がMLE。
メモ化部分を消して提出する。
WA
は~?! 考えても分からなそうなのでケースを見てみたら
勝利条件を見誤っていた。はみ出さなくても一番下の段につけばOKとのこと。
if (y >= 19) { // 18もOK! return 0; } if (x < 0 || 15 <= x || y < 0) { return INF; }
WA
^^ハゲそう
今度は
if (y >= 18) { return 0; } if (x < 0 || 15 <= x || y < 0) { return INF; }
としているのがよくなかった(下の段にいてもはみ出たらダメ)。
if (y >= 19) { return 0; } if (x < 0 || 15 <= x || y < 0) { return INF; } if (y >= 18) { return 0; }
これでよし!
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2361893#1
すぐにテストケースを見ないで考えておくべきだったなあ・・・。
反省。