Submission #976300

#TimeUsernameProblemLanguageResultExecution timeMemory
976300vjudge1Awesome Arrowland Adventure (eJOI19_adventure)C++17
100 / 100
71 ms9424 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define lld double #define int ll #define usaco(fname) freopen(#fname ".in","r",stdin);freopen(#fname ".out","w",stdout); template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } // const ll INF = 1e18; const int INF = 1e18; const int mod = 1e9+7; const lld PI = acos(-1.0); #define debug(x) cout << #x << ": " << x << endl; #define add(a, b) a += b, a %= mod #define mul(a, b) ((a % mod) * (b % mod)) % mod #define all(x) x.begin(),x.end() int tr(char x) { if (x == 'N') x = 'a'; else if ( x== 'E') x = 'b'; else if (x == 'S') x = 'c'; else x = 'd'; return x; } // get dist int dist(char a, char b) { int x = tr(a), y = tr(b); int ans = (y-x)%4; ans += 4; ans %= 4; return ans; } int di[] = {1, -1, 0, 0, 1, 1, -1, -1}; int dj[] = {0, 0, 1, -1, 1, -1, 1, -1}; char mapping[] = {'S', 'N', 'E', 'W'}; #define info tuple<int, int, int> void solve() { int n,m;cin>>n>>m; vector<string> grid(n); for (int i = 0; i < n; i++) cin >> grid[i]; // cost i j priority_queue<info, vector<info>, greater<info>> pq; pq.push({0, 0, 0}); vector<vector<int>> dp(n, vector<int>(m, INF)); while (!pq.empty()) { auto [cost, i, j] = pq.top();pq.pop(); dp[i][j] = min(dp[i][j], cost); if (grid[i][j] == 'X' || cost > dp[i][j]) continue; // cout << i << " " << j << endl; for (int k = 0; k < 4; k++) { int nexti = i + di[k], nextj = j + dj[k]; char dir = mapping[k]; int dis = dist(grid[i][j], dir); if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && cost+dis < dp[nexti][nextj]) { dp[nexti][nextj] = cost+dis; pq.push({cost + dis, nexti, nextj}); } } } cout << (dp[n-1][m-1] == INF ? -1 : dp[n-1][m-1]) << endl; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0); int t=1; while(t--) solve(); 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...