제출 #425109

#제출 시각아이디문제언어결과실행 시간메모리
425109MilosMilutinovicAwesome Arrowland Adventure (eJOI19_adventure)C++14
100 / 100
74 ms2884 KiB
#include <bits/stdc++.h> using namespace std; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1}; const int w[4][4] = { {0, 1, 2, 3}, {3, 0, 1, 2}, {2, 3, 0, 1}, {1, 2, 3, 0} }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<string> t(n); vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { cin >> t[i]; for (int j = 0; j < m; j++) { if (t[i][j] == 'N') a[i][j] = 0; if (t[i][j] == 'E') a[i][j] = 1; if (t[i][j] == 'S') a[i][j] = 2; if (t[i][j] == 'W') a[i][j] = 3; if (t[i][j] == 'X') a[i][j] = 4; } } multiset<tuple<int, int, int>> s; s.insert({0, 0, 0}); const int inf = 1e9; vector<vector<int>> dist(n, vector<int>(m, inf)); dist[0][0] = 0; while (!s.empty()) { auto it = s.begin(); auto val = *it; s.erase(it); int d = get<0>(val), x = get<1>(val), y = get<2>(val); if (a[x][y] == 4) { continue; } for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; int nd = d + w[a[x][y]][i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > nd) { if (dist[nx][ny] < inf) { s.erase({dist[nx][ny], nx, ny}); } dist[nx][ny] = nd; s.insert({dist[nx][ny], nx, ny}); } } } int ans = dist[n - 1][m - 1]; cout << (ans == inf ? -1 : ans) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...