#include<bits/stdc++.h>
using namespace std;
// JANGAN LUPA CEK PERLU LL NGGAK
#define pb push_back
#define pii pair<int,int>
#define fi first
#define inf INT_MAX
#define se second
#define ti tuple<int,int,int>
#define miku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int dis[501][501];
char a[501][501];
vector<char>arah={'N','E','S','W'};
vector<int>ax={-1,0,1,0};
vector<int>ay={0,1,0,-1};
signed main(){
miku
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
dis[i][j]=inf;
}
}
priority_queue<ti,vector<ti>,greater<ti>>q;
dis[1][1]=0;
q.push({0,1,1});
while(q.size()){
auto [d,x,y]=q.top();
q.pop();
if(dis[x][y]<d || a[x][y]=='X')continue;
int pos=0;
for(int i=0;i<4;i++) if(arah[i]==a[x][y]) pos=i;
for(int i=0;i<4;i++){
int npos=(pos+i)%4;
char c=arah[npos];
int nx=x+ax[npos];
int ny=y+ay[npos];
bool yes=0;
if(a[nx][ny]=='X' && (nx!=n|| ny!=m)) yes=1;
// cout<<"TIDAK "<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<d<<' '<<i<<" "<<c<<" "<<arah[pos]<<endl;
if(nx<1 || ny<1 || nx>n || ny>m || yes ||dis[nx][ny]<=d+i) continue;
// cout<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<d<<' '<<i<<" "<<c<<" "<<arah[pos]<<endl;
dis[nx][ny]=d+i;
q.push({d+i,nx,ny});
}
}
if(dis[n][m]==inf)cout<<-1;
else cout<<dis[n][m];
}
# | 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... |