Ice Climber (ZOJ Problem Set - 3555)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3555

問題

h*wの盤面のアイスクライマーで一番上にたどり着くまでの最小の時間を求めたい。ルールは以下のとおり。

• 左右に進むのにt1かかる
  • 敵がいる場合は無理
  • 進んだ先に足場がない場合も無理
  • 壁がある場合も無理
• 上のブロックを一つ壊すのにt2かかる
  • 足場がなくなった敵は消える
• ジャンプして上の段の一歩左か右の足場に乗るのにt2かかる
  • 先に真上のブロックを壊しておかなければならない
  • ジャンプ先に敵や壁がいる場合は無理
  • 足場がない場合も無理
  • 真上が壁の場合も無理
• 左右の敵を倒すのにt3かかる
  • 敵は動かない

1<=h<=4000
1<=w<=100

解法

ある段にたどり着いた瞬間に向いてる方向に進むしか意味が無いので、現在位置と向きを使ったメモ化再帰で解けば良い。敵の足場を消して倒すとかは意味が無い。