#include <bits/stdc++.h>
using namespace std;
const int N = 501;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
int arrow[N][N], dis[N][N], n, m;
int dijkstra() {
dis[1][1] = 0;
priority_queue<array<int, 3>> q;
q.push({ 0, 1, 1 });
while (q.size()) {
auto [d, x, y] = q.top();
q.pop();
d = -d;
if (x == n and y == m) {
return d;
}
if (d != dis[x][y] or arrow[x][y] == -1) {
continue;
}
for (int i = 0; i < 4; i++) {
int w = (i - arrow[x][y] + 4) % 4;
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 or n < nx or ny < 1 or m < ny) {
continue;
}
if (dis[nx][ny] > dis[x][y] + w) {
dis[nx][ny] = dis[x][y] + w;
q.push({ -dis[nx][ny], nx, ny });
}
}
}
return -1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
arrow[i][j] = (c == 'N' ? 0 : c == 'E' ? 1 : c == 'S' ? 2 : c == 'W' ? 3 : -1);
dis[i][j] = 1e9;
}
}
cout << dijkstra() << '\n';
}
# | 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... |