Submission #750286

#TimeUsernameProblemLanguageResultExecution timeMemory
7502867as__7Awesome Arrowland Adventure (eJOI19_adventure)C++17
0 / 100
5 ms4948 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define all(x) x.begin(),x.end() const int sz = 1e6 + 1, mod = 1e9 + 7, inf = -1e18; int dp[10001][1001] = {}; int change(char a, char b) { if (a == 'N') { int ans = 0; if (b == 'N')return ans; ans++; if (b == 'E')return ans; ans++; if (b == 'S')return ans; ans++; if (b == 'W')return ans; return ans; } if (a == 'W') { int ans = 0; if (b == 'W')return ans; ans++; if (b == 'N')return ans; ans++; if (b == 'E')return ans; ans++; if (b == 'S')return ans; return ans; } if (a == 'S') { int ans = 0; if (b == 'S')return ans; ans++; if (b == 'W')return ans; ans++; if (b == 'N')return ans; ans++; if (b == 'E')return ans; return ans; } if (a == 'E') { int ans = 0; if (a == 'E')return ans; ans++; if (b == 'S')return ans; ans++; if (b == 'W')return ans; ans++; if (b == 'N')return ans; return ans; } return 0; } signed main() { int n, m; cin >> n >> m; char a[502][502] = {}; int cost[502][502] = {}; vector<vector<int>>vc(n * m + 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; if (a[i][j] != 'X' && j > 1) { vc[m * (i - 1) + j].push_back(m * (i - 1) + j - 1); cost[m * (i - 1) + j][m * (i - 1) + j - 1] = change(a[i][j], 'W'); } if (a[i][j] != 'X' && j < m) { vc[m * (i - 1) + j].push_back(m * (i - 1) + j + 1); cost[m * (i - 1) + j][m * (i - 1) + j + 1] = change(a[i][j], 'E'); } if (a[i][j] != 'X' && i > 1) { vc[m * (i - 1) + j].push_back(m * (i - 2) + j); cost[m * (i - 1) + j][m * (i - 2) + j] = change(a[i][j], 'N'); } if (a[i][j] != 'X' && i < n) { vc[m * (i - 1) + j].push_back(m * (i)+j); cost[m * (i - 1) + j][m * (i)+j] = change(a[i][j], 'S'); } } } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; vector<int>ans(n * m + 1, 1e18); ans[1] = 0; pq.push({ 0,1 }); while (!pq.empty()) { int u = pq.top().second; int cos = pq.top().first; //cout << u << ' ' << cos << endl; pq.pop(); if (ans[u] < cos) { continue; } for (auto i : vc[u]) { if (cos + cost[u][i] < ans[i]) { ans[i] = cos + cost[u][i]; pq.push({ ans[i],i }); } } } cout << ans[m * (n)]; //cout << ans[m * (n - 1) + 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...