#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>, int> > adj[505][505];
priority_queue<pair<int, pair<int, int> > > pq;
int dist[505][505], final[505][505];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
dist[i][j]=1e9;
char c;
cin >> c;
if (c=='X')
continue;
int x, y;
if (c=='E')
x=0, y=1;
else if (c=='S')
x=1, y=0;
else if (c=='W')
x=0, y=-1;
else
x=-1, y=0;
for (int k=0; k<4; k++)
{
if (1<=i+x && i+x<=n && 1<=j+y && j+y<=m)
adj[i][j].push_back({{i+x, j+y}, k});
swap(x, y);
y=-y;
}
}
}
dist[1][1]=0;
pq.push({-dist[1][1], {1, 1}});
while (!pq.empty())
{
int ux=pq.top().second.first, uy=pq.top().second.second;
pq.pop();
if (final[ux][uy])
continue;
final[ux][uy]=1;
for (int i=0; i<adj[ux][uy].size(); i++)
{
int vx=adj[ux][uy][i].first.first, vy=adj[ux][uy][i].first.second, w=adj[ux][uy][i].second;
if (dist[vx][vy]>dist[ux][uy]+w)
{
dist[vx][vy]=dist[ux][uy]+w;
pq.push({-dist[vx][vy], {vx, vy}});
}
}
}
cout << (dist[n][m]<1e6?dist[n][m]:-1);
}
# | 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... |