いたずらっ子 - yukicoder No.971

#dp

最初, bfs で書いて tle した
1 マス移動するごとに一定の時間が加算されるとは限らないから, 同じマスを何度も踏むことがありうる
最初, i 回いたずらっ子のマスを踏んでからあるマスに到達し, 次に j (< i) 回いたずらっ子のマスを踏んでからそのマスに到達し, ...という風に

そもそもの, いたずらっ子のマスの扱いであるが,

時間を + 1 するところを, + 1 + i + j とすればいい $\ \ \ \ (1)$
(いたずらっ子のマス(i, j), 0 indexed)

∵
わざわざいたずらっ子のマスを踏んでスタートに帰って, 次はそのマスに行かないのでは行った意味がないから

dp で解く
dp なら, 同じマスを 2 度踏まない

dp[i][j] : マス(i, j) に到達する最短時間

更新は, 上の (1) の通り