This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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';
vis[n][m] = 1;
while(!q.empty()){
int i = q.top().ss.ff;
int j = q.top().ss.ss;
int w = q.top().ff;
if(i == 1 and j == 1) break;
// 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |