Submission #278481

#TimeUsernameProblemLanguageResultExecution timeMemory
278481acmAwesome Arrowland Adventure (eJOI19_adventure)C++14
100 / 100
147 ms21236 KiB
#include <bits/stdc++.h> #define speed \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define oprecision \ cout.precision(30); \ cerr.precision(7); #define ll long long #define ld long double #define ss string #define pii pair<int, int> #define pll pair<ll, ll> #define forn(n) for (int i = 1; i <= n; i++) #define forlr(l, r) \ for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++)) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define pb(x) push_back(x) #define pc(x) __builtin_popcount(x) #define pcll(x) __builtin_popcountll(x) #define mp(x, y) make_pair(x, y) #define F first #define S second using namespace std; int n, m, dp[5005][5005]; char a[5005][5005]; map<char, map<char, int>> cost; bool ok(int i, int j) { return ((1 <= i && i <= n) && (1 <= j && j <= m)); } int main() { speed; oprecision; // code cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; dp[i][j] = 1e9; } } dp[1][1] = 0; cost['W']['N'] = cost['N']['E'] = cost['E']['S'] = cost['S']['W'] = 1; cost['W']['E'] = cost['N']['S'] = cost['E']['W'] = cost['S']['N'] = 2; cost['W']['S'] = cost['N']['W'] = cost['E']['N'] = cost['S']['E'] = 3; cost['X']['S'] = cost['X']['N'] = cost['X']['E'] = cost['X']['W'] = 1e9; set<pair<int, pair<int, int>>> s; s.insert(mp(0, mp(1, 1))); // nswe while (sz(s)) { int i = s.begin()->S.F, j = s.begin()->S.S; s.erase(s.begin()); if (ok(i - 1, j) && dp[i - 1][j] > dp[i][j] + cost[a[i][j]]['N']) { dp[i - 1][j] = dp[i][j] + cost[a[i][j]]['N']; s.insert(mp(dp[i - 1][j], mp(i - 1, j))); } if (ok(i + 1, j) && dp[i + 1][j] > dp[i][j] + cost[a[i][j]]['S']) { dp[i + 1][j] = dp[i][j] + cost[a[i][j]]['S']; s.insert(mp(dp[i + 1][j], mp(i + 1, j))); } if (ok(i, j - 1) && dp[i][j - 1] > dp[i][j] + cost[a[i][j]]['W']) { dp[i][j - 1] = dp[i][j] + cost[a[i][j]]['W']; s.insert(mp(dp[i][j - 1], mp(i, j - 1))); } if (ok(i, j + 1) && dp[i][j + 1] > dp[i][j] + cost[a[i][j]]['E']) { dp[i][j + 1] = dp[i][j] + cost[a[i][j]]['E']; s.insert(mp(dp[i][j + 1], mp(i, j + 1))); } } cout << (dp[n][m] == 1e9 ? -1 : dp[n][m]); // endl #ifndef ONLINE_JUDGE cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif 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...