제출 #232162

#제출 시각아이디문제언어결과실행 시간메모리
232162Dremix10Awesome Arrowland Adventure (eJOI19_adventure)C++17
50 / 100
2085 ms49956 KiB
#include <bits/stdc++.h> using namespace std; struct ano{ int c; int d; bool operator<(const ano &o)const{ return d>o.d; } }; int main (){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; vector<vector<ano> > a(n*m,vector<ano>()); //int arr[n][m]; int i,j; //int cnt=0; for(i=0;i<n;i++) for(j=0;j<m;j++){ char c; cin>>c; if(c=='X') continue; if(c=='N'){ if(i-1>=0) a[i*m+j].push_back({(i-1)*m+j,0}); if(j+1<m) a[i*m+j].push_back({i*m+j+1,1}); if(i+1<n) a[i*m+j].push_back({(i+1)*m+j,2}); if(j-1>=0) a[i*m+j].push_back({i*m+j-1,3}); } else if(c=='E'){ if(i-1>=0) a[i*m+j].push_back({(i-1)*m+j,3}); if(j+1<m) a[i*m+j].push_back({i*m+j+1,0}); if(i+1<n) a[i*m+j].push_back({(i+1)*m+j,1}); if(j-1>=0) a[i*m+j].push_back({i*m+j-1,2}); } else if(c=='S'){ if(i-1>=0) a[i*m+j].push_back({(i-1)*m+j,2}); if(j+1<m) a[i*m+j].push_back({i*m+j+1,3}); if(i+1<n) a[i*m+j].push_back({(i+1)*m+j,0}); if(j-1>=0) a[i*m+j].push_back({i*m+j-1,1}); } else{ if(i-1>=0) a[i*m+j].push_back({(i-1)*m+j,1}); if(j+1<m) a[i*m+j].push_back({i*m+j+1,2}); if(i+1<n) a[i*m+j].push_back({(i+1)*m+j,3}); if(j-1>=0) a[i*m+j].push_back({i*m+j-1,0}); } } /* for(i=0;i<n*m;i++){ cout<<i<<" -> "; for(j=0;j<a[i].size();j++) cout<<a[i][j].c<<" - "<<a[i][j].d<<" "; cout<<endl; } */ priority_queue<ano> q; vector <int> d(n*m,10000000); q.push({0,0}); d[0]=0; while(!q.empty()){ int start=q.top().c; int w=q.top().d; q.pop(); //cout<<start<<endl; if(d[start]<w) continue; for(auto x : a[start]) if(d[x.c]>d[start]+x.d){ d[x.c]=d[start]+x.d; q.push(x); } } if(d[n*m-1]==10000000) cout<<-1<<endl; else cout<<d[n*m-1]<<endl; }
#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...