#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
#define pqueue priority_queue
using namespace std;
using namespace __gnu_pbds;
constexpr int MAX = 5e+2 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
int temp, temp1, temp2, temp3;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
vector <vector <char>> v(MAX, vector <char>(MAX));
vector <vector <int>> dis(MAX, vector <int>(MAX, INF));
int get(char xx, int y) {
int x;
if (xx == 'X') return 1e+7;
if (xx == 'N') x = 0;
if (xx == 'E') x = 1;
if (xx == 'S') x = 2;
if (xx == 'W') x = 3;
return (y >= x ? y - x : y - x + 4);
}
void dijkstra(int n, int m) {
pqueue <pair<pair<int, int>, int>, vector <pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> pq;
pq.push({{0, 0}, 0});
dis[0][0]= 0;
while (!pq.empty()) {
auto x = pq.top();
pq.pop();
auto u = x.ff;
int d = x.ss;
if (dis[u.ff][u.ss] != d) continue;
if (v[u.ff][u.ss] == 'X') continue;
for (int j=0; j < 4; j++) {
pair<int, int> i = {u.ff + dx[j], u.ss + dy[j]};
if (i.ff < 0 || i.ff >= n || i.ss < 0 || i.ss >= m) continue;
if (v[i.ff][i.ss] == 'X' && i.ff != n-1 && i.ss != m-1) continue;
int g = get(v[u.ff][u.ss], j);
if (dis[i.ff][i.ss] > dis[u.ff][u.ss] + g) {
dis[i.ff][i.ss] = dis[u.ff][u.ss] + g;
pq.push({i, dis[i.ff][i.ss]});
}
}
}
}
void _() {
int n, m;
cin >> n >> m;
dis.assign(n, vector <int>(m, INF));
for (int i=0; i < n; i++) {
for (int j=0; j < m; j++) {
cin >> v[i][j];
}
}
dijkstra(n, m);
cout << (dis[n-1][m-1] > n * m * 4 ? -1 : dis[n-1][m-1]);
}
signed main() {
GOOD_LUCK
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
freopen("log.txt", "w", stderr);
srand(time(0));
int tests=1;
// cin >> tests;
for (int i=1; i <= tests; i++) {
// cout << "Case #" << i << ": "
_();
// cout << endl;
}
// int n;
// while (cin >> n) {
// _(n);
// cout << endl;
// }
return 0;
}
// Problem X
// by Ekber_Ekber
/*
1
7
0100101
*/
Compilation message (stderr)
adventure.cpp: In function 'int main()':
adventure.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen("log.txt", "w", stderr);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |