# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1127990 | heey | Awesome Arrowland Adventure (eJOI19_adventure) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[200005];
struct g{int x, y, t;};
bool cmp(g l, g r){
return l.t < r.t;
}
int df(char cur, char dir){
if(cur == dir) return 0;
if(cur == 'N') return 1 + df('E', dir);
if(cur == 'E') return 1 + df('S', dir);
if(cur == 'S') return 1 + df('W', dir);
if(cur == 'W') return 1 + df('N', dir);
return 0;
}
signed main(){
//ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<char>> a(n, vector<char>(m));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
vector<vector<int>> d(n, vector<int>(m, INT_MAX));
vector<vector<bool>> u(n, vector<bool>(m, false));
d[0][0] = 0;
multiset<g, decltype(&cmp)> pick(cmp);
pick.insert({0, 0, 0});
while(!pick.empty()){
//if(d[n-1][m-1] != INT_MAX) break;
int x, y;
g cur = *pick.begin();
pick.erase(pick.find(cur));
x = cur.x;
y = cur.y;
if(d[x][y] == INT_MAX) break;
if(u[x][y]) continue;
u[x][y] = true;
if(a[x][y] == 'X') continue;
if(x > 0) {
int tm = d[x][y] + df(a[x][y], 'N');
if(d[x-1][y] > tm){
d[x-1][y] = tm;
pick.insert({x-1, y, tm});
}
}
if(x < n-1){
int tm = d[x][y] + df(a[x][y], 'S');
if(d[x+1][y] > tm){
d[x+1][y] = tm;
pick.insert({ x+1, y, tm});
}
}
if(y > 0) {
int tm = d[x][y] + df(a[x][y], 'W');
if(d[x][y-1] > tm){
d[x][y-1] = tm;
pick.insert({ x, y-1, tm});
}
}
if(y < m-1) {
int tm = d[x][y] + df(a[x][y], 'E');
if(d[x][y+1] > tm){
d[x][y+1] = tm;
pick.insert({x, y+1, tm});
}
}
}
if(d[n-1][m-1] == INT_MAX) cout << "-1";
else cout << d[n-1][m-1];
return 0;
}