This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
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-1;
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-1;
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-1;
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-1;
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<<ex<<' '<<ey<<'\n';
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<ans[i][j]<<' ';
}
cout<<'\n';
}
*/
cout<<ans[ex][ey]<<'\n';
}
# | 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... |