Submission #735039

#TimeUsernameProblemLanguageResultExecution timeMemory
735039josanneo22Portals (BOI14_portals)C++17
0 / 100
10 ms16212 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define pipii pair<int,pair<int,int>> const int maxn=1005; int n,m,sx,sy,ex,ey; int ans[maxn][maxn],a[maxn][maxn],up[maxn][maxn],down[maxn][maxn],lf[maxn][maxn],rt[maxn][maxn]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; bool valid(int x,int y){ if(x>=0 && x<=n-1 && y>=0 && y<=m-1 && a[x][y]==1) return true; else return false; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); /* this task just looks like djikstra, only hard part if to determine up,down,lf,rt of each i,j */ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ char x; cin>>x; if(x=='#')a[i][j]=0; else a[i][j]=1; if(x=='S'){ sx=i;sy=j; } if(x=='C'){ ex=i;ey=j; } } } for(int i=0;i<maxn;i++){ for(int j=0;j<maxn;j++){ up[i][j]=-1; down[i][j]=-1; lf[i][j]=-1; rt[i][j]=-1; } } for(int i=0;i<n;i++){ up[0][i]=0; down[n-1][i]=0; } for(int i=0;i<m;i++){ rt[i][m-1]=0; lf[i][0]=0; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]==0){ int tx=i-1,ty=j,ok=1; while(tx>=0 && ok){ if(down[tx][ty]==-1 && a[tx][ty]!=0){ down[tx][ty]=i-tx; tx--; } else ok=0; } tx=i+1,ty=j,ok=1; while(tx<=n-1 && ok){ if(up[tx][ty]==-1 && a[tx][ty]!=0){ up[tx][ty]=tx-i; tx++; } else ok=0; } tx=i,ty=j+1,ok=1; while(ty<=m-1 && ok){ if(lf[tx][ty]==-1&& a[tx][ty]!=0){ lf[tx][ty]=ty-j; ty++; } else ok=0; } tx=i,ty=j-1,ok=1; while(ty>=0 && ok){ if(rt[tx][ty]==-1&& a[tx][ty]!=0){ rt[tx][ty]=j-ty; ty--; } else ok=0; } } } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(up[i][j]==-1) up[i][j]=i; if(down[i][j]==-1) down[i][j]=n-i-1; if(lf[i][j]==-1) lf[i][j]=j; if(rt[i][j]==-1) rt[i][j]=m-j-1; } } priority_queue<pipii,vector<pipii>,greater<pipii>> pq; pq.push(mp(0,mp(sx,sy))); for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j]=1e9; while(pq.size()){ pair<int,pair<int,int>> u=pq.top(); pq.pop(); if(!valid(u.se.fi,u.se.se)) continue; if(ans[u.se.fi][u.se.se]<=u.fi) continue; ans[u.se.fi][u.se.se]=u.fi; for(int i=0;i<4;i++){ if(valid(u.se.fi+dx[i],u.se.se+dy[i])) pq.push(mp(u.fi+1,mp(u.se.fi+dx[i],u.se.se+dy[i]))); } pq.push(mp(u.fi+1,mp(u.se.fi-up[u.se.fi][u.se.se],u.se.se))); pq.push(mp(u.fi+1,mp(u.se.fi+down[u.se.fi][u.se.se],u.se.se))); pq.push(mp(u.fi+1,mp(u.se.fi,u.se.se-lf[u.se.fi][u.se.se]))); pq.push(mp(u.fi+1,mp(u.se.fi,u.se.se+rt[u.se.fi][u.se.se]))); } cout<<ans[ex][ey]<<'\n'; }
#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...