제출 #448513

#제출 시각아이디문제언어결과실행 시간메모리
448513mychecksedadAwesome Arrowland Adventure (eJOI19_adventure)C++17
34 / 100
5 ms6348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int N = 505; #define pii pair<int,int> #define pb push_back struct Edge{ int x, y, w; }; int n, m, dist[N][N]; char c; vector<Edge> g[N][N]; bool vis[N][N]; int main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> n >> m; int arr[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; for(int i = 0; i <= n+2; i++) for(int j = 0; j <= m+2; j++) {dist[i][j] = 1e9; vis[i][j] = 0;} Edge e; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> c; int co; if(c == 'N'){ co = 0; for(int k = 0; k < 4; k++){ e.x = i + arr[(k+co)%4][0]; e.y = j + arr[(k+co)%4][1]; e.w = k; g[i][j].pb(e); } }else if(c == 'E'){ co=1; for(int k = 0; k < 4; k++){ e.x = i + arr[(k+co)%4][0]; e.y = j + arr[(k+co)%4][1]; e.w = k; g[i][j].pb(e); } }else if(c == 'S'){ co=2; for(int k = 0; k < 4; k++){ e.x = i + arr[(k+co)%4][0]; e.y = j + arr[(k+co)%4][1]; e.w = k; g[i][j].pb(e); } }else if(c == 'W'){ co=3; for(int k = 0; k < 4; k++){ e.x = i + arr[(k+co)%4][0]; e.y = j + arr[(k+co)%4][1]; e.w = k; g[i][j].pb(e); } } } } dist[1][1] = 0; priority_queue<pair<int, pii>> q; q.push({0, {1, 1}}); while(!q.empty()){ int x = q.top().second.first, y = q.top().second.second; q.pop(); if(vis[x][y]) continue; vis[x][y] = 1; for(Edge u: g[x][y]){ if(!vis[u.x][u.y] && dist[x][y] + u.w < dist[u.x][u.y]){ dist[u.x][u.y] = dist[x][y] + u.w; q.push({-u.w, {u.x, u.y}}); } } } cout << (!vis[n][m] ? -1 : dist[n][m]); 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...