#include<bits/stdc++.h>
using namespace std;
int dir[4][2] ={
{0,-1}, //N
{1,0}, // E
{0,1},// S
{-1,0}// W
};
#define X -1
int val(char C){
if(C=='N')return 0;
if(C=='E')return 1;
if(C=='S')return 2;
if(C=='W')return 3;
return X;
};
struct node{
int x,y,cost;
};
bool operator<(node a,node b){
return a.cost>b.cost;
}
int width,height;
bool in(int x,int y){
return (x>=0 && y>=0 && x<width && y<height);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>height>>width;
char tab[width][height];
bool mem[width][height];
for(int y=0;y<height;y++){
string line;cin>>line;
for(int x=0;x<width;x++){
mem[x][y] = false;
tab[x][y] = line[x];
}
}
priority_queue<node> PQ;
PQ.push({0,0,0});
while(!PQ.empty()){
node act = PQ.top();PQ.pop();
if(mem[act.x][act.y])continue;
mem[act.x][act.y]=true;
int direction = val(tab[act.x][act.y]);
//On jette les croix
if(act.x==width-1 && act.y==height-1){
cout<<act.cost<<endl;
return 0;
}
if(direction==X)continue;
for(int d=0;d<4;d++){
int D = (direction+d)%4;
//On calcul les voisins
int vx = act.x + dir[D][0];
int vy = act.y + dir[D][1];
if(in(vx,vy) && !mem[vx][vy]){
PQ.push({vx,vy,act.cost+d});
}
}
}
cout<<-1<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
320 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
320 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
260 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
292 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
320 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
260 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
320 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
316 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
0 ms |
212 KB |
Output is correct |
| 31 |
Correct |
0 ms |
316 KB |
Output is correct |
| 32 |
Correct |
1 ms |
292 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
3 ms |
340 KB |
Output is correct |
| 36 |
Correct |
0 ms |
324 KB |
Output is correct |
| 37 |
Correct |
3 ms |
324 KB |
Output is correct |
| 38 |
Correct |
0 ms |
340 KB |
Output is correct |
| 39 |
Correct |
33 ms |
1120 KB |
Output is correct |
| 40 |
Correct |
34 ms |
1100 KB |
Output is correct |
| 41 |
Correct |
1 ms |
968 KB |
Output is correct |
| 42 |
Correct |
36 ms |
1100 KB |
Output is correct |
| 43 |
Correct |
34 ms |
4212 KB |
Output is correct |
| 44 |
Correct |
1 ms |
964 KB |
Output is correct |
