#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
using namespace std;
int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
int n,m,i,j,k;
char a[505][505];
bool vis[505][505];
int dist[505][505];
struct nod{
int cost;
int x;
int y;
};
int cost(char x, int y)
{
if(y>=x)return y-x;
return 4+y-x;
}
struct cmp{
bool operator () ( nod a, nod b )
{
return a.cost > b.cost;
}
};
priority_queue<nod,vector<nod>,cmp> q;
void solve()
{
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>(a[i]+1);
for(j=1;j<=m;j++)
{
if(a[i][j]=='X')a[i][j]=0;
if(a[i][j]=='N')a[i][j]=1;
if(a[i][j]=='E')a[i][j]=2;
if(a[i][j]=='S')a[i][j]=3;
if(a[i][j]=='W')a[i][j]=4;
dist[i][j]=1e9;
}
}
q.push({0,1,1});
dist[1][1]=0;
while(!q.empty())
{
nod top = q.top();
q.pop();
int x=top.x;
int y=top.y;
int c=top.cost;
if(vis[x][y]||!a[x][y])continue;
vis[x][y]=1;
for(k=1;k<5;k++)
{
int nx=x+dx[k];
int ny=y+dy[k];
int nc=c+cost(a[x][y],k);
if(nc<dist[nx][ny])
{
dist[nx][ny]=nc;
q.push({nc,nx,ny});
}
}
}
cout<<dist[n][m]<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
328 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 |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
