#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ins insert
#define pb push_back
#define piii pair<int,pair<int,int>>
#define pii pair<int,int>
void solve(){
int n;cin>>n;
int st,stt,g,gg;cin>>st>>stt>>g>>gg;
vector<int>a(n);
for(int &d:a) cin>>d;
vector<vector<vector<pii>>>adj(n+1,vector<vector<pii>>(5003));
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i-1]+1;j++){
if(i!=1&&j==1){
adj[i][j].pb({i-1,a[i-2]+1});
}
if(i!=n&&j==a[i-1]+1){
adj[i][j].pb({i+1,1});
}
if(j!=1){
adj[i][j].pb({i,j-1});
}
if(j!=a[i-1]+1){
adj[i][j].pb({i,j+1});
}
if(i!=1){
adj[i][j].pb({i-1,j});
}
if(i!=n){
adj[i][j].pb({i+1,j});
}
}
}/*
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i-1]+1;j++){
for(auto el:adj[i][j]){
cout<<el.first<<'/'<<el.second<<' ';
}
cout<<endl;
}
cout<<endl;
}
*/
vector<vector<int>>dist(n+1,vector<int>(5003,int(1e9+2e6)));
priority_queue<piii,vector<piii>,greater<piii>>pq;
pq.push({0,{st,stt}});
while(pq.size()){
auto [d,p]=pq.top();pq.pop();
//cout<<p.first<<'/'<<p.second<<endl;
if(d>=dist[p.first][p.second]) continue;
dist[p.first][p.second]=d;
if(p.first==g&&p.second==gg) break;
for(auto ne:adj[p.first][p.second]){
if(d+1<dist[ne.first][ne.second]){
//cout<<"next:"<<ne.first<<' '<<ne.second<<' '<<d<<endl;
pq.push({d+1,{ne.first,ne.second}});
}
}
}
cout<<dist[g][gg]<<endl;
}
int main() {
int t=1;
while(t--)solve();
}
# | 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... |