Let \(\text{dist}[i][j]\) be the minimum number of moves when the piece starts from cell \((i,j)\). If it is unreachable from cell \((i,j)\), let \(\text{dist}[i][j]=\infty\).

First, for the goal cells \((R_i,C_i)\) \((1 \leq i \leq K)\), we have \(\text{dist}[R_i][C_i]=0\).

For the other cells, \(dist[i][j]\) is the second smallest value among \(dist[i-1][j]+1,dist[i][j-1]+1,dist[i+1][j]+1\), and \(dist[i][j+1]+1\), because Aoki blocks one of Takahashi’s optimal moving direction.

However, these recurrence relations have a dependency loop when we want the value \(\text{dist}[i][j]\). Instead, consider filling these \(\text{dist}\) values in reverse order of progression of the game, starting from the goal state. This is widely known as backtracking.

We find \(dist\) in ascending order of move counts required. First of all, we determine that \(\text{dist}[R_i][C_i]=0\) for the goal cells. Every cell \((i,j)\) whose at least two adjacent cells have determined values is ready to determine the value \(dist[i][j]\) itself. Therefore, we maintain for each cell the number of adjacent cells that have determined values, while keep determining the values \(\text{dist}\) until there is no other place to update. This procedure yields the final \(\text{dist}\). By the way, when \(\text{dist}[i][j]\) is determined for some cell \((i,j)\), the only cells whose values \(\text{dist}\) can be newly determined are those adjacent to \((i,j)\). Therefore, \(\text{dist}\) can be found in a total of \(\mathrm{O}(NM)\) time.

Similar problem: ABC209E - Shiritori

Sample code (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)); // Minimum number of moves required to reach the goal when starting from cell (i,j)
    vector<vector<int>> cnt(h, vector<int>(w, 0)); // Among adjacent cells, how many of them have determined dist values?
    queue<pair<int, int>> que; // Queue of cells with determined 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 is undetermined, but at least two adjacent cells have determined dist, so dist can be determined
                dist[nx][ny] = dist[x][y] + 1;
                que.emplace(nx, ny);
            }
        }
    }
    cout << ans << "\n";
}