ARC019 C問題
解法
スタート地点からほこらまでの最短距離、ほこらからゴール地点までの最短距離を求めることで答えが求まる。
途中の敵の数を減らすために、経由地点xを追加し、
スタート->x->ほこら->x->ゴール
という順序ですすむようにする。
スタート、ほこら、ゴールからそれぞれBSFで最短距離を計算することで時間内に計算することができる。
経由地点xに敵がいる場合は、3つ余分に数えているのでその分を考慮する。
計算量
O(RCK)
コード
補足
動的計画法を用いて、dp[h][k][r][c]
h:ほこらを通ったかどうか
k:敵を倒した回数
r:R
c:C
とした場合メモ化により一見O(KRC)で計算できるように見えるが、あるマスでの最小値を求めるための更新が必要となるためO(KRC)とはならずにTLEする。
