まず、マグマが \(1\) つも無い場合を考えます。この場合、幅優先探索を用いて計算量 \(O(HW)\) で解くことができます。幅優先探索については この問題 を参考にしてください。

次に、マグマがある場合を考えます。マグマはプレイヤーの動きによらずどのように浸食するかが決まっているため、先にマグマの挙動を求めます。

\(\mathrm{magma}[i][j] =\) マグマが \((i,j)\) に到達するまでの最短時間

とすると、多始点の幅優先探索を用いることで、すべての \(1 \leq i \leq H, 1 \leq j \leq W\) に対する \(\mathrm{magma}[i][j]\) を \(O(HW)\) で求めることができます。

これを求めた上で、

\(\mathrm{player}[i][j] =\) プレイヤーが \((i,j)\) に到達するまでの最短時間

を求めます。これは、先ほどの幅優先探索に「プレイヤーの進もうとする先にマグマが浸食していたら進めない」という条件を追加することで計算量 \(O(HW)\) で解くことができます。よってこの問題を計算量 \(O(HW)\) で解くことができました。

• 実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<char>> grid(h,vector<char>(w));
    for(int i = 0;i < h;i++) {
        for(int j = 0;j < w;j++) {
            cin >> grid[i][j];
        }
    }

    vector<int> dy = {-1, 1, 0, 0};
    vector<int> dx = {0, 0, -1, 1};

    queue<pair<pair<int, int>, int>> que_magma;
    vector<vector<int>> dist_magma(h, vector<int>(w, 1000000000));
    for(int i = 0;i < h;i++) {
        for(int j = 0;j < w;j++) {
            if(grid[i][j] == '@') {
                que_magma.push({{i, j}, 0});
                dist_magma[i][j] = 0;
            }
        }
    }

    while(not que_magma.empty()) {
        auto [v, d] = que_magma.front();
        que_magma.pop();
        auto [y, x] = v;
        if(dist_magma[y][x] < d) continue;

        for(int i = 0;i < 4;i++) {
            int next_y = y + dy[i];
            int next_x = x + dx[i];
            if(0 <= next_y && next_y < h && 0 <= next_x && next_x < w && grid[next_y][next_x] == '.' && dist_magma[next_y][next_x] > dist_magma[y][x] + k) {
                dist_magma[next_y][next_x] = dist_magma[y][x] + k;
                que_magma.push({{next_y, next_x}, dist_magma[next_y][next_x]});
            }
        }
    }

    queue<pair<pair<int, int>, int>> que_player;
    vector<vector<int>> dist_player(h, vector<int>(w, 1000000000));
    que_player.push({{0, 0}, 0});
    dist_player[0][0] = 0;

    while(not que_player.empty()) {
        auto [v, d] = que_player.front();
        que_player.pop();
        auto [y, x] = v;
        if(dist_player[y][x] < d) continue;

        for(int i = 0;i < 4;i++) {
            int next_y = y + dy[i];
            int next_x = x + dx[i];
            if(0 <= next_y && next_y < h && 0 <= next_x && next_x < w && grid[next_y][next_x] == '.' && dist_player[next_y][next_x] > dist_player[y][x] + 1 && dist_player[y][x] + 1 < dist_magma[next_y][next_x]) {
                dist_player[next_y][next_x] = dist_player[y][x] + 1;
                que_player.push({{next_y, next_x}, dist_player[next_y][next_x]});
            }
        }
    }

    if(dist_player[h - 1][w - 1] != 1000000000) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}