AOJ 2612 : Phutball

Phutball | Aizu Online Judge

状態数は少なそうなので普通に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


すぐにテストケースを見ないで考えておくべきだったなあ・・・。
反省。