제출 #882093

#제출 시각아이디문제언어결과실행 시간메모리
882093spetar76Awesome Arrowland Adventure (eJOI19_adventure)C++17
100 / 100
78 ms22472 KiB
#include <bits/stdc++.h> using namespace std; #define maxn 250052 int v,n,m,e; int ind(int i, int j) { return (i-1)*n+j; } vector<pair<int,int>> adj[maxn]; int dist[maxn]; bool pos[maxn]; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; void dijkstra(int pocetan) { //dist[pocetan]=0; for (int i=0; i<=n*m; ++i){ dist[i]=-1; } q.push(make_pair(0, pocetan)); while (!q.empty()){ pair<int,int> x=q.top(); q.pop(); if (!pos[x.second]){ dist[x.second]=x.first; pos[x.second]=true; for (auto i:adj[x.second]){ if (!pos[i.first]){ q.push(make_pair(x.first + i.second, i.first)); } } } } return; } int main() { cin>>m>>n; int a[m+1][n+1]; for (int i=1; i<=m; ++i){ string st; cin>>st; for (int j=0; j<n; ++j){ if (st[j]=='X'){a[i][j+1]=-1;} else if (st[j]=='E'){a[i][j+1]=0;} else if (st[j]=='S'){a[i][j+1]=1;} else if (st[j]=='W'){a[i][j+1]=2;} else{a[i][j+1]=3;} } } for (int i=1; i<=m; ++i){ for (int j=1; j<=n; ++j){ if (j<n && a[i][j]>=0){ adj[ind(i,j)].push_back(make_pair(ind(i,j+1), (4-a[i][j])%4)); } if (j>1 && a[i][j]>=0){ adj[ind(i,j)].push_back(make_pair(ind(i,j-1), (6-a[i][j])%4)); } if (i>1 && a[i][j]>=0){ adj[ind(i,j)].push_back(make_pair(ind(i-1,j), (7-a[i][j])%4)); } if (i<m && a[i][j]>=0){ adj[ind(i,j)].push_back(make_pair(ind(i+1,j), (5-a[i][j])%4)); } } } dijkstra(1); cout<<dist[m*n]; 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...