Submission #1090243

#TimeUsernameProblemLanguageResultExecution timeMemory
1090243MuhammetAwesome Arrowland Adventure (eJOI19_adventure)C++17
38 / 100
1 ms456 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second int n, m, vis[505][505]; char v[] = {'N', 'E', 'S', 'W'}; vector <vector <char>> a; vector <vector <int>> dp; int f(char x, char y){ int ind = 0; for(int i = 0; i < 4; i++){ if(v[i] == x){ ind = i; break; } } int cnt = 0; while(1){ if(v[ind] == y) break; ind++; if(ind == 4) ind = 0; cnt++; } return cnt; } int main(){ cin >> n >> m; a.assign(n+1, vector <char> (m+1)); dp.assign(n+1, vector <int> (m+1,1e9)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; } } priority_queue <pair<int,pair<int,int>>> q; q.push({0,{n,m}}); for(int i = 0; i <= n+1; i++){ vis[i][0] = vis[i][m+1] = 1; } for(int i = 0; i <= m+1; i++){ vis[0][i] = vis[n+1][i] = 1; } dp[n][m] = 0; a[n][m] = 'E'; while(!q.empty()){ int i = q.top().ss.ff; int j = q.top().ss.ss; int w = q.top().ff; // cout << i << ' ' << j << ' ' dp[i][j] << '\n'; w *= (-1); q.pop(); if((a[i][j] == 'X') or (dp[i][j] != w)) continue; if(vis[i][j+1] == 0 and f(a[i][j+1],'W')+dp[i][j] < dp[i][j+1]){ dp[i][j+1] = f(a[i][j+1],'W')+dp[i][j]; q.push({-dp[i][j+1],{i,j+1}}); } if(vis[i][j-1] == 0 and f(a[i][j-1],'E')+dp[i][j] < dp[i][j-1]){ dp[i][j-1] = f(a[i][j-1],'E')+dp[i][j]; q.push({-dp[i][j-1],{i,j-1}}); } if(vis[i+1][j] == 0 and f(a[i+1][j],'N')+dp[i][j] < dp[i+1][j]){ dp[i+1][j] = f(a[i+1][j],'N')+dp[i][j]; q.push({-dp[i+1][j],{i+1,j}}); } if(vis[i-1][j] == 0 and f(a[i-1][j],'S')+dp[i][j] < dp[i-1][j]){ dp[i-1][j] = f(a[i-1][j],'S')+dp[i][j]; q.push({-dp[i-1][j],{i-1,j}}); } } cout << (dp[1][1] == 1e9 ? -1 : dp[1][1]); }
#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...