Submission #962590

#TimeUsernameProblemLanguageResultExecution timeMemory
962590AtabayRajabliAwesome Arrowland Adventure (eJOI19_adventure)C++17
100 / 100
20 ms8536 KiB
#include <bits/stdc++.h> // author : a1abay #define all(v) v.begin(), v.end() #define GCD(a, b) __gcd(a, b) #define LCM(a, b) (a*b / (__gcd(a, b))) #define int ll typedef long long ll; const int inf = 1e9 + 7; const int inff = (int)1e18 + 7; const int sz = 5e2 + 5; using namespace std; int n, m; int a[sz][sz]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; bool ok(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); map<char, int> mp; mp['N'] = 0; mp['E'] = 1; mp['S'] = 2; mp['W'] = 3; mp['X'] = 4; cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char c; cin >> c; a[i][j] = mp[c]; } } queue<array<int, 2>> q[4]; q[0].push({1, 1}); vector<vector<int>> d(n + 1, vector<int>(m + 1, inf)); d[1][1] = 0; int pos = 0, num = 1; while(num > 0) { while(q[pos].empty()) { pos = (pos + 1) % 4; } int x = q[pos].front()[0], y = q[pos].front()[1]; q[pos].pop(); num--; if(a[x][y] == 4)continue; for(int i = 0; i < 4; i++) { int vx = dx[i] + x; int vy = dy[i] + y; if(!ok(vx, vy))continue; int w = (i <= a[x][y] ? (i + 4 - a[x][y]) % 4 : i - a[x][y]); if(d[vx][vy] > d[x][y] + w) { d[vx][vy] = d[x][y] + w; q[d[vx][vy] % 4].push({vx, vy}); num++; } } } if(d[n][m] >= inf)d[n][m] = -1; cout << d[n][m]; }
#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...