#include <bits/stdc++.h>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
const int sz = 5e5;
const ll INF = 1e18;
ll n, m;
#define pii pair<ll,ll>
vector<vector<pii>>gra;
vector<ll> dist;
bitset<sz>done;
void solve(int su) {
for (int i = 0; i < n*m; i++) {
dist[i] = INF;
}
dist[su] = 0;
priority_queue<pii, vector<pii>, greater<pii>>pq;
pq.push({ 0,su });
while (!pq.empty()) {
pii tmp = pq.top();
pq.pop();
ll u = tmp.second, d = tmp.first;
if (done[u])
continue;
done[u] = true;
for (auto ii : gra[tmp.second]) {
ll v = ii.first, w = ii.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({ dist[v],v });
}
}
}
}
int main() {
cin >> n >> m;
vector<vector<char>>vec1(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> vec1[i][j];
}
}
vector<vector<int>>vec(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (vec1[i][j] == 'N')
vec[i][j] = 1;
if (vec1[i][j] == 'E')
vec[i][j] = 2;
if (vec1[i][j] == 'S')
vec[i][j] = 3;
if (vec1[i][j] == 'W')
vec[i][j] = 4;
}
}
int tmp = 0;
dist.resize(n * m);
gra.resize(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i != 0) {
gra[tmp].push_back({ tmp - m,abs(vec[i][j] - 1) });
}
if (i != n - 1) {
if (vec[i][j] > 3)
gra[tmp].push_back({ tmp + m,4 - abs(vec[i][j] - 3) });
else
gra[tmp].push_back({ tmp + m,abs(vec[i][j] - 3) });
}
if (j != m - 1) {
if (vec[i][j] > 2)
gra[tmp].push_back({ tmp + 1,4 - abs(vec[i][j] - 2) });
else
gra[tmp].push_back({ tmp + 1,abs(vec[i][j] - 2) });
}
if (j != 0) {
gra[tmp].push_back({ tmp - 1 ,abs(vec[i][j] - 4) });
}
tmp++;
}
}
solve(0);
if (dist[n * m - 1] == INF)
cout << -1;
else
cout << dist[n * m - 1];
}
Compilation message
adventure.cpp: In function 'void solve(int)':
adventure.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < n*m; i++) {
| ~~^~~~~
adventure.cpp:22:22: warning: unused variable 'd' [-Wunused-variable]
22 | ll u = tmp.second, d = tmp.first;
| ^
adventure.cpp: In function 'int main()':
adventure.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < n; i++) {
| ~~^~~
adventure.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
39 | for (int j = 0; j < m; j++) {
| ~~^~~
adventure.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < n; i++) {
| ~~^~~
adventure.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
45 | for (int j = 0; j < m; j++) {
| ~~^~~
adventure.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < n; i++) {
| ~~^~~
adventure.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
60 | for (int j = 0; j < m; j++) {
| ~~^~~
adventure.cpp:64:10: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
64 | if (i != n - 1) {
| ~~^~~~~~~~
adventure.cpp:70:10: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
70 | if (j != m - 1) {
| ~~^~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
