Submission #1197828

#TimeUsernameProblemLanguageResultExecution timeMemory
1197828HanksburgerAwesome Arrowland Adventure (eJOI19_adventure)C++20
100 / 100
89 ms26808 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<pair<int, int>, int> > adj[505][505]; priority_queue<pair<int, pair<int, int> > > pq; int dist[505][505], final[505][505]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { dist[i][j]=1e9; char c; cin >> c; if (c=='X') continue; int x, y; if (c=='E') x=0, y=1; else if (c=='S') x=1, y=0; else if (c=='W') x=0, y=-1; else x=-1, y=0; for (int k=0; k<4; k++) { if (1<=i+x && i+x<=n && 1<=j+y && j+y<=m) adj[i][j].push_back({{i+x, j+y}, k}); swap(x, y); y=-y; } } } dist[1][1]=0; pq.push({-dist[1][1], {1, 1}}); while (!pq.empty()) { int ux=pq.top().second.first, uy=pq.top().second.second; pq.pop(); if (final[ux][uy]) continue; final[ux][uy]=1; for (int i=0; i<adj[ux][uy].size(); i++) { int vx=adj[ux][uy][i].first.first, vy=adj[ux][uy][i].first.second, w=adj[ux][uy][i].second; if (dist[vx][vy]>dist[ux][uy]+w) { dist[vx][vy]=dist[ux][uy]+w; pq.push({-dist[vx][vy], {vx, vy}}); } } } cout << (dist[n][m]<1e6?dist[n][m]:-1); }
#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...