Untitled
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