Submission #1344231

#TimeUsernameProblemLanguageResultExecution timeMemory
1344231ElayV13Text editor (CEOI24_editor)C++20
0 / 100
35 ms39616 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF=1e18;

int n;
int sl,sc,el,ec;
int l[1001];
int dd[1001][5001];

pair<int,int> R(int x,int y){
      if(y+1<=l[x]) return {x,y+1};
      if(x==n) return {-1,-1};
      return {x+1,1};
}
pair<int,int> L(int x,int y){
      if(y-1>=1) return {x,y-1};
      if(x==1) return {-1,-1};
      return {x-1,l[x-1]+1};
}
pair<int,int> U(int x,int y){
      if(x-1<=0) return {-1,-1};
      return {x-1,min(y,l[x-1]+1)};
}
pair<int,int> D(int x,int y){
      if(x+1>n) return {-1,-1};
      return {x+1,min(y,l[x+1]+1)};
}

bool can(pair<int,int>p,pair<int,int>v){
      if(dd[p.first][p.second]==INF&&p.first!=-1&&p.second!=-1&&dd[p.first][p.second]>dd[v.first][v.second]+1) return 1;
      return 0;
}

void bfs(int x,int y){
      dd[x][y]=0;
      queue<pair<int,int>>q;
      q.push({x,y});
      while(!q.empty()){
            pair<int,int>v=q.front();
            q.pop();    
            int x=v.first;
            int y=v.second;
            pair<int,int>g1=R(x,y);
            pair<int,int>g2=L(x,y);
            pair<int,int>g3=U(x,y);
            pair<int,int>g4=D(x,y);
            if(can(g1,v)){
                  dd[g1.first][g1.second]=dd[x][y]+1;
                  q.push(g1);
            }
            if(can(g2,v)){
                  dd[g2.first][g2.second]=dd[x][y]+1;
                  q.push(g2);
            }
            if(can(g3,v)){
                  dd[g3.first][g3.second]=dd[x][y]+1;
                  q.push(g3);
            }
            if(can(g4,v)){
                  dd[g4.first][g4.second]=dd[x][y]+1;
                  q.push(g4);
            }
      }
}

signed main(){
      for(int i=0;i<1001;i++) for(int j=0;j<5001;j++) dd[i][j]=INF;
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
      cin>>n;
      cin>>sl>>sc>>el>>ec;
      for(int i=1;i<=n;i++) cin>>l[i];
      bfs(sl,sc);
      cout<<dd[el][ec]<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...