#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll sz = 1e6;
const ll INF = 1e18;
ll n, m;
#define pii pair<ll,ll>
vector<vector<pii>>gra;
vector<ll> dist;
bitset<sz>done;
void solve(ll su) {
for (ll 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;
if (n == 0 or m == 0)
cout << -1;
else {
vector<vector<char>>vec1(n, vector<char>(m));
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
cin >> vec1[i][j];
}
}
vector<vector<ll>>vec(n, vector<ll>(m));
for (ll i = 0; i < n; i++) {
for (ll 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;
}
}
ll tmp = 0;
dist.resize(n * m);
gra.resize(n * m);
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
if (vec1[i][j] != 'X') {
if (i != 0) {
gra[tmp].push_back({ tmp - m,vec[i][j] - 1 });
}
if (i != n - 1) {
if (vec[i][j] > 3)
gra[tmp].push_back({ tmp + m,4 - (vec[i][j] - 3) });
else
gra[tmp].push_back({ tmp + m,3 - vec[i][j] });
}
if (j != m - 1) {
if (vec[i][j] > 2)
gra[tmp].push_back({ tmp + 1,4 - (vec[i][j] - 2) });
else
gra[tmp].push_back({ tmp + 1,2 - vec[i][j] });
}
if (j != 0) {
gra[tmp].push_back({ tmp - 1 ,4 - vec[i][j] });
}
}
tmp++;
}
}
solve(0);
if (dist[tmp - 1] == INF)
cout << 0;
else
cout << dist[tmp - 1];
}
}
Compilation message
adventure.cpp: In function 'void solve(ll)':
adventure.cpp:21:22: warning: unused variable 'd' [-Wunused-variable]
21 | ll u = tmp.second, d = tmp.first;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
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 |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
