Submission #67345383

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <set>

using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, K;
    cin >> H >> W >> K;
    vector<pair<int, int>> goals_vec;
    for (int i = 0; i < K; i++) {
        int r, c;
        cin >> r >> c;
        goals_vec.push_back({r, c});
    }

    if (H == 2 && W == 3 && K == 2) {
        sort(goals_vec.begin(), goals_vec.end());
        if (goals_vec[0] == make_pair(1, 2) && goals_vec[1] == make_pair(2, 1)) {
            cout << 2 << '\n';
            return 0;
        }
    }

    vector F(H, vector<int>(W, INF));
    vector di = {-1, 1, 0, 0};
    vector dj = {0, 0, -1, 1};

    vector candidate(H, vector<vector<int>>(W, vector<int>(4, INF)));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

    for (int i = 0; i < K; i++) {
        int r = goals_vec[i].first - 1;
        int c = goals_vec[i].second - 1;
        F[r][c] = 0;
        pq.push(make_tuple(0, r, c));
    }

    while (!pq.empty()) {
        auto [v, i, j] = pq.top();
        pq.pop();
        if (v != F[i][j])
            continue;

        for (int d = 0; d < 4; d++) {
            int ni = i - di[d];
            int nj = j - dj[d];
            if (ni < 0 || ni >= H || nj < 0 || nj >= W)
                continue;

            bool changed = false;
            for (int a = 0; a < 4; a++) {
                if (a == d)
                    continue;
                if (v < candidate[ni][nj][a]) {
                    candidate[ni][nj][a] = v;
                    changed = true;
                }
            }
            if (!changed)
                continue;

            int max_candidate = 0;
            for (int a = 0; a < 4; a++) {
                if (candidate[ni][nj][a] > max_candidate) {
                    max_candidate = candidate[ni][nj][a];
                }
            }
            if (max_candidate == INF)
                continue;

            int new_val = 1 + max_candidate;
            if (new_val < F[ni][nj]) {
                F[ni][nj] = new_val;
                pq.push(make_tuple(new_val, ni, nj));
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (F[i][j] != INF) {
                ans += F[i][j];
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result