#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const char c[4] = {'N', 'E', 'S', 'W'};
int n, m, ans = 1e9;
vector<string> v;
map<char, int> id;
bool inside(int i, int j) {
return i >= 0 && i < n && j >= 0 && j < m;
}
bool solvable() {
if (v[0][0] == 'X') return 0;
vector<vector<bool>> vis(n, vector<bool>(m, 0));
queue<pair<int, int>> bfs;
bfs.push({0, 0});
vis[0][0] = 1;
while (!bfs.empty()) {
auto [x, y] = bfs.front();
bfs.pop();
if (v[x][y] == 'X') continue;
if (inside(x + 1, y)) {
bfs.push(make_pair(x + 1, y));
vis[x + 1][y] = 1;
}
if (inside(x, y + 1)) {
bfs.push(make_pair(x, y + 1));
vis[x][y + 1] = 1;
}
}
return vis[n-1][m-1];
}
int dist(char a, char b) {
int ret = (id[b] - id[a]) % 4;
if (ret < 0) ret += 4;
return ret;
}
int f(tuple<int, int, int, int, int> a) {
auto [g, i, j, ii, jj] = a;
return g;
}
signed main() {
id['N'] = 1;
id['E'] = 2;
id['S'] = 3;
id['W'] = 4;
cin >> n >> m;
v.resize(n);
for (int i = 0; i<n; i++) {
cin >> v[i];
}
if (n == 1 && m == 1) {
cout << 0 << '\n';
return 0;
}
if (!solvable()) {
cout << -1 << '\n';
return 0;
}
auto cmp = [&](tuple<int, int, int, int, int> &a, tuple<int, int, int, int, int> &b) {
return f(a) > f(b);
};
priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, decltype(cmp)> pq(cmp);
pq.push({0, 0, 0, -1, -1});
while (!pq.empty()) {
auto [g, i, j, ii, jj] = pq.top();
pq.pop();
if (i == n-1 && j == m-1) {
ans = g;
break;
}
if (v[i][j] == 'X') continue;
for (int k = 0; k < 4; k++) {
if (inside(i + dx[k], j + dy[k]) && (i + dx[k] != ii || j + dy[k] != jj))
pq.push({g + dist(v[i][j], c[k]), i + dx[k], j + dy[k], i, j});
}
}
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
436 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
436 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
436 KB |
Output is correct |
| 17 |
Correct |
1 ms |
684 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
1343 ms |
102400 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
436 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
436 KB |
Output is correct |
| 17 |
Correct |
1 ms |
684 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Runtime error |
1343 ms |
102400 KB |
Execution killed with signal 9 |
| 27 |
Halted |
0 ms |
0 KB |
- |
