| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 976671 | 2024-05-07T02:06:50 Z | vjudge1 | Awesome Arrowland Adventure (eJOI19_adventure) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
#define endl '\n'
#define pii pair<int, pair<int, int>>
using namespace std;
int N,M,a[505][505];
int cost[505][505];
pair<int, int> dir[4];
mpp<char, int> mp;
char c;
pqriority_queue<pii, vector<pii>, greater<pii>> pq;
void solve() {
cin >> N >> M;
mp['N'] = 0;
mp['E'] = 1;
mp['S'] = 2;
mp['W'] = 3;
mp['X'] = -1;
dir[0] = {-1, 0}; // N
dir[1] = {0, 1}; // E
dir[2] = {1, 0}; // W
dir[3] = {0, -1};
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> c;
a[i][j] = mp[c];
cost[i][j] = 1e9;
}
}
cost[1][1] = 0;
pq.push({0, {1, 1}});
while (!pq.empty()) {
int cur = pq.top().f;
int icur = pq.top().s.f;
int jcur = pq.top().s.s;
// cout << cur << ' ' << icur << ' ' << jcur << endl;
pq.pop();
if (icur == N && jcur == M) {
cout << cur << endl;
return;
}
if (a[icur][jcur] == -1) continue;
if (cur > cost[icur][jcur]) continue;
for (int cst = 0; cst < 4; cst++) {
auto dr = dir[(a[icur][jcur] + cst) % 4];
int inxt = icur + dr.f;
int jnxt = jcur + dr.s;
int cnxt = cur + cst;
if (inxt >= 1 && inxt <= N && jnxt >= 1 && jnxt <= M && cost[inxt][jnxt] > cnxt) {
cost[inxt][jnxt] = cnxt;
pq.push({cnxt, {inxt, jnxt}});
}
}
}
cout << -1 << endl;
}
signed mpin() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
}