Untitled

mail@pastecode.io avatar
unknown
c_cpp
20 days ago
2.7 kB
5
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define Task "BIETTHU"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second

typedef pair<int, int> ii;

const int N = 2e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

int numRow, numCol, numButton;
int X[N], Y[N];
ll dp[N][2];
vector<int> hor[N], ver[N];

struct State {
    ll dist;
    int u, dir;
};

bool valid(int x, int y) {
    return x >= 1 && x <= numRow && y >= 1 && y <= numCol;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }

    cin >> numCol >> numRow >> numButton;
    FOR(i, 1, numButton)
        cin >> X[i] >> Y[i];

    if (numButton == numRow * numCol) {
        cout << numRow - 1 + numCol - 1 + 1;
        return 0;
    }

    FOR(i, 1, numButton) {
        ver[X[i]].push_back(i);
        hor[Y[i]].push_back(i);
    }

    queue<State> q;
    memset(dp, 0x3f, sizeof(dp));
    FOR(i, 1, numButton) {
        if (X[i] == 1) {
            dp[i][0] = Y[i] - 1;
            q.push({dp[i][0], i, 0});
        }
    }


    ll ans = 1LL * INF * INF;
    while (!q.empty()) {
        auto [dist, u, dir] = q.front();
        q.pop();
        if (dp[u][dir] < dist) continue;
        if (Y[u] == numRow) {
            minimize(ans, dp[u][dir] + abs(numCol - X[u]) + (dir == 0 ? 1 : 0));
        }
        if (X[u] == numCol) {
            minimize(ans, dp[u][dir] + abs(numRow - Y[u]) + (dir == 1 ? 1 : 0));
        }

        for (int idx : ver[X[u]]) {
            ll newDist = dp[u][dir] + abs(Y[u] - Y[idx]) + (dir == 1 ? 1 : 0);
            if (dp[idx][0] > newDist) {
                dp[idx][0] = newDist;
                q.push({dp[idx][0], idx, 0});
            }
        }
        for (int idx : hor[Y[u]]) {
            ll newDist = dp[u][dir] + abs(X[u] - X[idx]) + (dir == 0 ? 1 : 0);
            if (dp[idx][1] > newDist) {
                dp[idx][1] = newDist;
                q.push({dp[idx][1], idx, 1});
            }
        }
    }

    cout << (ans == 1LL * INF * INF ? -1 : ans);

    return 0;
}


Leave a Comment