#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
long long n,m;
vector<pair< long long, long long> > adj[4000];
char a[505][505];
char c[4]={'N','E','S','W'};
bool bound(long long x,long long y){
if(x<0 || y<0 || x>=n || y>=m){
return 0;
}
return 1;
}
long long dp[505][505];
long long dif(char x, char y){
long long ix=0,iy=0;
if(x=='X'){
return 1e9;
}
for(long long i=0; i<4; i++){
if(c[i]==x){
ix=i;
}
}
for(long long i=0; i<4; i++){
if(c[i]==y){
iy=i;
}
}
if(ix<=iy){
return iy-ix;
}else{
return 4-ix+iy;
}
}
void solve(){
priority_queue<pair<long long, pair<long long,long long> > > q;
dp[0][0]=0;
q.push({0,{0,0}});
while(q.size()!=0){
pair<long long,long long> te=q.top().s;
long long x=te.f;
long long y=te.s;
if(dp[x][y]<=(q.top().f)){
q.pop();
continue;
}
/*
if(vis[te.s]==true){
q.pop();
continue;
}*/
q.pop();
long long t1=dp[x][y]+dif(a[x][y], 'W');
long long t2=dp[x][y]+dif(a[x][y], 'N');
long long t3=dp[x][y]+dif(a[x][y], 'S');
long long t4=dp[x][y]+dif(a[x][y], 'E');
if(bound(x,y-1)){
if(t1<dp[x][y-1]){
dp[x][y-1]=t1;
// cout<<x<<" "<<y-1<<" dp "<<dp[x][y-1]<<endl;
q.push({-t1, {x,y-1}});
}
}
if(bound(x-1,y)){
if(t2<dp[x-1][y]){
dp[x-1][y]=t2;
q.push({-t2, {x-1,y}});
// cout<<x-1<<" "<<y<<" dp "<<dp[x-1][y]<<endl;
}
}
if(bound(x+1,y)){
if(t3<dp[x+1][y]){
dp[x+1][y]=t3;
q.push({-t3, {x+1,y}});
// cout<<x+1<<" "<<y<<" dp "<<dp[x+1][y]<<endl;
}
}
if(bound(x,y+1)){
if(t4<dp[x][y+1]){
dp[x][y+1]=t4;
q.push({-t4, {x,y+1}});
// cout<<x<<" "<<y+1<<" dp "<<dp[x][y+1]<<endl;
}
}
}
cout<<dp[n-1][m-1];
}
int main(){
cin>>n>>m;
for (long long i = 0; i < n; i++){
for (long long j = 0; j < m; j++){
cin >> a[i][j];
dp[i][j] = 1e9;
}
}
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
