제출 #966307

#제출 시각아이디문제언어결과실행 시간메모리
966307rahidilbayramliAwesome Arrowland Adventure (eJOI19_adventure)C++17
100 / 100
101 ms48064 KiB
#pragma GCC optimize("-O3") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define pii pair<int, int> #define all(v) v.begin(), v.end() #define rall(v) v.begin(), v.end() #define pb push_back #define p_b pop_back #define f first #define s second using namespace std; const ll sz = 600; vector<pair<pll, ll>>g[sz][sz]; ll dist[sz][sz], vis[sz][sz]; void dijkstra(pll node) { for(ll i = 0; i < sz; i++) { for(ll j = 0; j < sz; j++) dist[i][j] = 0x3F3F3F3F; } dist[node.f][node.s] = 0; priority_queue<pair<ll, pll>>pq; pq.push({0, {node.f, node.s}}); while(!pq.empty()) { ll a = pq.top().s.f, b = pq.top().s.s; pq.pop(); if(vis[a][b]) continue; vis[a][b] = 1; for(auto [u, w] : g[a][b]) { if(dist[u.f][u.s] > dist[a][b] + w) { dist[u.f][u.s] = dist[a][b] + w; pq.push({-dist[u.f][u.s], u}); } } } } void solve() { ll n, m, i, j; cin >> n >> m; char grid[n+5][m+5]; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) cin >> grid[i][j]; } // E, S, W, N for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { if(grid[i][j] == 'W') { if(j - 1 >= 1) g[i][j].pb({{i, j - 1}, 0}); if(j + 1 <= m) g[i][j].pb({{i, j + 1}, 2}); if(i - 1 >= 1) g[i][j].pb({{i - 1, j}, 1}); if(i + 1 <= n) g[i][j].pb({{i + 1, j}, 3}); } else if(grid[i][j] == 'N') { if(j - 1 >= 1) g[i][j].pb({{i, j - 1}, 3}); if(j + 1 <= m) g[i][j].pb({{i, j + 1}, 1}); if(i - 1 >= 1) g[i][j].pb({{i - 1, j}, 0}); if(i + 1 <= n) g[i][j].pb({{i + 1, j}, 2}); } else if(grid[i][j] == 'E') { if(j - 1 >= 1) g[i][j].pb({{i, j - 1}, 2}); if(j + 1 <= m) g[i][j].pb({{i, j + 1}, 0}); if(i - 1 >= 1) g[i][j].pb({{i - 1, j}, 3}); if(i + 1 <= n) g[i][j].pb({{i + 1, j}, 1}); } else if(grid[i][j] == 'S') { if(j - 1 >= 1) g[i][j].pb({{i, j - 1}, 1}); if(j + 1 <= m) g[i][j].pb({{i, j + 1}, 3}); if(i - 1 >= 1) g[i][j].pb({{i - 1, j}, 2}); if(i + 1 <= n) g[i][j].pb({{i + 1, j}, 0}); } } } dijkstra({1, 1}); cout << (dist[n][m] == 0x3F3F3F3F ? -1 : dist[n][m]) << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tests = 1; //cin >> tests; while(tests--) { solve(); } }
#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...