#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
int n,m;
vector<pair< int, int> > adj[4000];
char a[505][505];
char c[4]={'N','E','S','W'};
bool bound(int x,int y){
if(x<0 || y<0 || x>=n || y>=m){
return 0;
}
return 1;
}
int dp[505][505];
int dif(char x, char y){
int ix,iy;
if(x=='X'){
return 1e9;
}
for(int i=0; i<4; i++){
if(c[i]==x){
ix=i;
}
}
for(int 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<int, pair<int,int> > > q;
dp[0][0]=0;
q.push({0,{0,0}});
while(q.size()!=0){
pair<int,int> te=q.top().s;
int x=te.f;
int y=te.s;
if(dp[x][y]<-(q.top().f)){
q.pop();
continue;
}
/*
if(vis[te.s]==true){
q.pop();
continue;
}*/
q.pop();
int t1=dp[x][y]+dif(a[x][y], 'W');
int t2=dp[x][y]+dif(a[x][y], 'N');
int t3=dp[x][y]+dif(a[x][y], 'S');
int 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 (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[i][j];
dp[i][j] = 1e9;
}
}
solve();
}
Compilation message
adventure.cpp: In function 'int dif(char, char)':
adventure.cpp:36:13: warning: 'iy' may be used uninitialized in this function [-Wmaybe-uninitialized]
36 | return iy-ix;
| ^~
adventure.cpp:36:13: warning: 'ix' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
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 |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 4 |
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 |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
