コマがマス \((i,j)\) にある状態から始めたときにゴールに到達するまでの移動回数の最小値を \(\text{dist}[i][j]\) とします。ただし、ゴールに到達できないマス \((i,j)\) については \(\text{dist}[i][j]=\infty\) とします。

まずゴールのマス\((R_i,C_i)\) \((1 \leq i \leq K)\) については \(\text{dist}[R_i][C_i]=0\) です。

そうでないマスについては \(dist[i][j]\) は\(dist[i-1][j]+1,dist[i][j-1]+1,dist[i+1][j]+1,dist[i][j+1]+1\) を昇順に並べ替えたときに 小さい方から \(2\) 番目の値となります。青木君が高橋君にとって最適な方向のうち \(1\) 方向への移動を禁止することができることから言えます。

しかし、この遷移からでは \(\text{dist}[i][j]\) を求める際に条件がループしてしまいます。そこで、ゴールに到達した状態からゲームを逆順に進めていくことで \(\text{dist}\) を求めていくことを考えます。これは一般に後退解析と呼ばれます。

移動回数が小さい順に \(dist\) を求めていきます。初め、ゴールマスについて \(\text{dist}[R_i][C_i]=0\) と確定させます。 隣接するマスのうち \(2\) マス以上で \(dist\) の値が確定しているマス \((i,j)\) について、先ほどの事実から \(dist[i][j]\) の値も確定させることができます。よって、各マスについて隣接するマスのうち\(dist\) が求まっているマスの個数を管理しながら、 更新する箇所がなくなるまで \(\text{dist}\) の値を確定させていくと最終的に \(\text{dist}\) が求まります。 また、あるマス \((i,j)\) について \(\text{dist}[i][j]\) が確定したことによって、\(\text{dist}\) の値が確定しうるマスは \((i,j)\) に隣接するマスのみです。したがって、BFSをすることで \(\text{dist}\) を時間計算量 \(\mathrm{O}(NM)\) で求めることができます。

類題: ABC209E - Shiritori

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<int>> dist(h, vector<int>(w, -1)); // マス (i,j) から始めたときにゴールに到達するまでの移動回数の最小値
    vector<vector<int>> cnt(h, vector<int>(w, 0)); // 隣接するマスのうちdistが決定したマスが何個あるか
    queue<pair<int, int>> que; // distが確定したマスのキュー
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        dist[x][y] = 0;
        cnt[x][y] = 4;
        que.emplace(x, y);
    }
    long long ans = 0;
    while (!que.empty()) {
        auto [x, y] = que.front();
        que.pop();
        ans += dist[x][y];
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                continue;
            cnt[nx][ny]++;
            if (dist[nx][ny] == -1 && cnt[nx][ny] == 2) {
                // distが確定しておらず、隣接するマスのうちdistが決定しているマスが2マス存在するためdistが確定する
                dist[nx][ny] = dist[x][y] + 1;
                que.emplace(nx, ny);
            }
        }
    }
    cout << ans << "\n";
}