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 OYY 1000000000005
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mid (start+end)/2
#define mod 1000000007
int n,m,dizi[505][505],uzak[505][505];
int cev=0,a,b;
char sor[505][505];
void dijk(){
priority_queue <pair<int,pair<int,int>>> q;//
q.push({0,{0,0}});
while(!q.empty()){
int a=q.top().second.first;
int b=q.top().second.second;
int cost=q.top().first;
q.pop();
if((a<0 || a>=m || b<0 || b>=n)){//SINIR dışında
continue;
}
if(uzak[b][a]!=-1)continue;
uzak[b][a]=cost;
if(dizi[b][a]==-1)continue;
for(int i=0;i<4;i++){
int gx=(dizi[b][a]+i)%4;
int gy=(dizi[b][a]+i)%4;
if(gx==0)gx=0;
if(gx==1)gx=1;
if(gx==2)gx=0;
if(gx==3)gx=-1;
//////////////////////////////////////////////////////////////
if(gy==0)gy=-1;
if(gy==1)gy=0;
if(gy==2)gy=1;
if(gy==3)gy=0;
q.push({-(cost+i),{a+gx,b+gy}});
}
}
}
int32_t main(){
// faster
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>sor[i][j];
char h=sor[i][j];
if(h=='N')dizi[i][j]=0;
else if(h=='E')dizi[i][j]=1;
else if(h=='S')dizi[i][j]=2;
else if(h=='W')dizi[i][j]=3;
else if(h=='X')dizi[i][j]=-1;
uzak[i][j]=-1;
}
}
if(n==1){
cev=0;
bool stop=true;
for(int i=0;i<n && stop;i++){
for(int j=0;j<m && stop;j++){
if(sor[i][j]=='X'){
if(!(i==n-1 && j==m-1)){
cev=-1;
stop=false;
}
}
else if(sor[i][j]=='N'){
cev++;
}
else if(sor[i][j]=='S'){
cev+=3;
}
else if(sor[i][j]=='W'){
cev+=2;
}
else continue;
}
}
cout<<cev<<'\n';
return 0;
}
dijk();
cout<<-1*uzak[n-1][m-1]<<'\n';
return 0;
}
# | 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... |