제출 #494594

#제출 시각아이디문제언어결과실행 시간메모리
494594uncriptedAwesome Arrowland Adventure (eJOI19_adventure)C++11
100 / 100
104 ms8960 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back long long n,m; char a[505][505]; char c[4]={'N','E','S','W'}; bool bound(long long x,long long y){ if(x<0 || y<0 || x>=n || y>=m){ return 0; } return 1; } long long dp[505][505]; long long dif(char x, char y){ long long ix=0,iy=0; if(x=='X'){ return 1e9; } for(long long i=0; i<4; i++){ if(c[i]==x){ ix=i; } } for(long long i=0; i<4; i++){ if(c[i]==y){ iy=i; } } if(ix<=iy){ return iy-ix; }else{ return 4-ix+iy; } } void solve(){ priority_queue<pair<long long, pair<long long,long long> > > q; dp[0][0]=0; q.push({0,{0,0}}); while(q.size()!=0){ pair<long long,long long> te=q.top().s; long long x=te.f; long long y=te.s; if(dp[x][y]!=-(q.top().f)){ q.pop(); continue; } /* if(vis[te.s]==true){ q.pop(); continue; }*/ q.pop(); long long t1=dp[x][y]+dif(a[x][y], 'W'); long long t2=dp[x][y]+dif(a[x][y], 'N'); long long t3=dp[x][y]+dif(a[x][y], 'S'); long long t4=dp[x][y]+dif(a[x][y], 'E'); if(bound(x,y-1)){ if(t1<dp[x][y-1]){ dp[x][y-1]=t1; // cout<<x<<" "<<y-1<<" dp "<<dp[x][y-1]<<endl; q.push({-t1, {x,y-1}}); } } if(bound(x-1,y)){ if(t2<dp[x-1][y]){ dp[x-1][y]=t2; q.push({-t2, {x-1,y}}); // cout<<x-1<<" "<<y<<" dp "<<dp[x-1][y]<<endl; } } if(bound(x+1,y)){ if(t3<dp[x+1][y]){ dp[x+1][y]=t3; q.push({-t3, {x+1,y}}); // cout<<x+1<<" "<<y<<" dp "<<dp[x+1][y]<<endl; } } if(bound(x,y+1)){ if(t4<dp[x][y+1]){ dp[x][y+1]=t4; q.push({-t4, {x,y+1}}); // cout<<x<<" "<<y+1<<" dp "<<dp[x][y+1]<<endl; } } } if(dp[n-1][m-1]>=1e9){ cout<<"-1"; }else{ cout<<dp[n-1][m-1]; } } int main(){ cin>>n>>m; for (long long i = 0; i < n; i++){ for (long long j = 0; j < m; j++){ cin >> a[i][j]; dp[i][j] = 1e9; } } 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...