이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
const char nl = '\n';
void fastIO() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};
const int MAX = 5005;
int main() {
fastIO();
int N;
cin>>N;
ll x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
x1--; y1--; x2--; y2--;
vi L(N, 0);
for (int i = 0; i < N; i++) {
cin>>L[i];
L[i]++;
}
map<ii, ll> dist;
queue<ii> q; // {x, y}
q.push({x1, y1});
dist[{x1, y1}] = 0;
int ctr = 0;
while (!q.empty()) {
ctr++;
if (ctr == 200)
break;
ii p = q.front();
// cout<<"at "<<p.fi<<", "<<p.se<<endl;
q.pop();
for (int i = 0; i < 4; i++) {
ll nx = p.fi + dirX[i];
ll ny = p.se + dirY[i];
if (nx < 0 || nx >= N) // can't go up / down when at edge
continue;
if (nx == 0 && ny == -1) // can't go left at start
continue;
if (nx == N - 1 && ny == L[N - 1]) // can't go right at end
continue;
// convert to actual become
if (ny == L[nx] && i == 3) {
nx++;
ny = 0;
}
else if (ny == -1 && i == 2) {
nx--;
ny = L[nx] - 1;
}
if (i == 0 || i == 1)
ny = min(ny, L[nx] - 1);
if (dist[{nx, ny}] == 1e9) {
// cout<<"going to "<<nx<<" "<<ny<<endl;
dist[{nx, ny}] = dist[{p.fi, p.se}] + 1;
q.push({nx, ny});
}
}
}
ll ans = 1e18;
for (pair<ii, ll> p : dist) {
ans = min(ans, abs(p.fi.fi - x2) + abs(p.fi.se - y2) + p.se);
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |