#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
vector<char> d = {'S','E','N','W'};
const int inf = LLONG_MAX/2;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
map<char,map<char,int>> dist;
dist['N']['S'] = 2;
dist['S']['N'] = 2;
dist['E']['W'] = 2;
dist['W']['E'] = 2;
dist['W']['S'] = 3;
dist['N']['W'] = 3;
dist['E']['N'] = 3;
dist['S']['E'] = 3;
for (auto i:d){
for (auto j:d){
if (i == j) dist[i][j] = 0;
else if (!dist[i].count(j)) dist[i][j] = 1;
}
}
/*for (auto i:dist){
for (auto j:i.second){
cout << i.first << ' ' << j.first << ' ' << j.second << '\n';
}
}*/
vector<string> v(n);
for (int i=0; i<n; ++i) cin >> v[i];
vector<vector<int>> vu(n,vector<int>(m,inf));
priority_queue<tuple<int,int,int>> q;
q.emplace(0,0,0);
vu[0][0] = 0;
while (!q.empty()){
auto f = q.top();
int x,y,a;
tie(a,x,y) = f;
q.pop();
for (int i=0; i<4; ++i){
int nx = dir[i].first + x, ny = dir[i].second + y;
a += dist[v[x][y]][d[i]];
if (nx >= 0 and ny >= 0 and nx < n and ny < m and vu[nx][ny] > a){
vu[nx][ny] = a;
if (v[nx][ny] != 'X') q.emplace(a,nx,ny);
}
a -= dist[v[x][y]][d[i]];
}
}
if (vu[n-1][m-1] == inf) cout << -1;
else cout << vu[n-1][m-1];
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
0 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
0 ms |
384 KB |
Output is correct |
| 20 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
12 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Correct |
41 ms |
504 KB |
Output is correct |
| 6 |
Correct |
30 ms |
384 KB |
Output is correct |
| 7 |
Correct |
9 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
0 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
0 ms |
384 KB |
Output is correct |
| 20 |
Correct |
0 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
0 ms |
384 KB |
Output is correct |
| 24 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
