AT_abc413_f [ABC413F] No Passage

因为题目询问每个 $(i,j)$ 作为起点的情况，故考虑从终点开始进行 $\text{BFS}$ ，将 $K$ 个终点全都入队，跑一个多起始点的最短路。

因为双方都会采取最佳策略，所以显然对方选择禁用的方向都会此时己方最优的方向，即距离终点最近的方向，所以再每次扩展时都选择距离的次小值进行扩展。

因为每次走一格，相当于是一张无向无权图，直接使用 $\text{BFS}$ 即可，代码使用了 $\text{Dijkstra}$ ，实际没有必要。

复杂度 $O(nm\ log (nm))$ ，使用 $\text{BFS}$ 可以使复杂度降为 $O(nm)$

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

using i64 = long long;
#define endl '\n'
#define xx first
#define yy second

int _x[] = {1, -1, 0, 0};
int _y[] = {0, 0, 1, -1};

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> ed(k);
    for (auto &i : ed)
        cin >> i.xx >> i.yy;

    auto check = [&](int x, int y) -> bool
    {
        return x >= 1 && x <= n && y >= 1 && y <= m;
    };

    auto dijkstra = [&]() -> vector<vector<int>>
    {
        vector<vector<int>> dis(n + 1, vector<int>(m + 1, {numeric_limits<int>::max()}));
        vector<vector<bool>> vis(n + 1, vector<bool>(m + 1, false));
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> que;
        for (auto &[x, y] : ed)
        {
            dis[x][y] = 0;
            que.push({0, {x, y}});
        }
        while (!que.empty())
        {
            auto [x, y] = que.top().yy;
            que.pop();
            if (vis[x][y])
                continue;
            vis[x][y] = 1;
            for (int i = 0; i < 4; i++)
            {
                int xx = x + _x[i];
                int yy = y + _y[i];
                if (!check(xx, yy))
                    continue;
                array<int, 4> pre;
                for (int z = 0; z < 4; z++)
                {
                    int nx = xx + _x[z];
                    int ny = yy + _y[z];
                    pre[z] = check(nx, ny) ? dis[nx][ny] : numeric_limits<int>::max();
                }
                sort(pre.begin(), pre.end());
                int temp = pre[1] == numeric_limits<int>::max() ? numeric_limits<int>::max() : pre[1] + 1;
                if (dis[xx][yy] > temp)
                {
                    dis[xx][yy] = temp;
                    que.push({dis[xx][yy], {xx, yy}});
                }
            }
        }
        return dis;
    };
    auto dis = dijkstra();
    i64 ans = 0;
    for (int i = 1; i <= n; i++)
        for (int z = 1; z <= m; z++)
            ans += dis[i][z] == numeric_limits<int>::max() ? 0 : dis[i][z];
    cout << ans << endl;

    return 0;
}