いたずらっ子 [yukicoder 971]

https://yukicoder.me/problems/no/971

解説

https://yukicoder.me/submissions/418655

まず、重要な性質に気づく必要がある。
「いたずらっ子によって最初の場所に戻されたとしても、始点から終点まで通るパスは、毎回同じである。」
戻されたときに違うルートを通った方が最適な場合は最初からそのルートを通るのが最適であるためである。

あとは、DPで計算していく。
dp[y][x] := 区間(y, x)に移動するのにかかる最短時間
移動はy++かx++しかないので、グラフはDAGとなる。
よって、ダイクストラまでは必要なく、DPで計算すればいい。
いたずらっ子によるロスタイムは、区間(y,x)で捕まったら、(x+y)である(x,yは0-indexed)。

int H, W;
string A[2020];
int dp[2020][2020];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];

    rep(y, 0, H) rep(x, 0, W) dp[y][x] = inf;
    dp[0][0] = 0;

    rep(y, 0, H) rep(x, 0, W) {
        int d = A[y][x] == 'k' ? x + y : 0;
        if (x) chmin(dp[y][x], dp[y][x - 1] + 1 + d);
        if (y) chmin(dp[y][x], dp[y - 1][x] + 1 + d);
    }

    cout << dp[H - 1][W - 1] << endl;
}