#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <queue>
#include <string>
#include <limits>
#include <map>
#include <algorithm>
#include <stack>
using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
int n, m;
int dist[510][510];
char g[510][510];
bool done[510][510] = {false};
map<char, pair<int,int>> dir = { {'E', {0,1}}, {'S', {1,0}}, {'W', {0,-1}}, {'N', {-1,0}} };
map<char, char> kov = { {'E', 'S'}, {'S', 'W'}, {'W', 'N'}, {'N', 'E'}};
vector<pair<int,pair<int,int>>> neighbour(pair<int,int> p){
if(g[p.first][p.second] == 'X'){
return {};
}
vector<pair<int,pair<int,int>>> v;
char c = g[p.first][p.second];
int cost = 0;
do{
pair<int,int> index = {p.first + dir[c].first, p.second + dir[c].second};
if(index.first >= 0 && index.first < n && index.second >= 0 && index.second < m){
v.push_back({cost, index});
}
++cost;
c = kov[c];
}while(c != g[p.first][p.second]);
return v;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
dist[i][j] = mod;
cin >> g[i][j];
}
}
dist[0][0] = 0;
priority_queue<pair<int,pair<int,int>>> q;
q.push({0,{0,0}});
while(!q.empty()){
auto s = q.top().second;
q.pop();
if(done[s.first][s.second]) continue;
done[s.first][s.second] = true;
vector<pair<int,pair<int,int>>> v = neighbour(s);
for(auto i : v){
auto coordinate = i.second;
if(dist[coordinate.first][coordinate.second] > dist[s.first][s.second] + i.first){
dist[coordinate.first][coordinate.second] = dist[s.first][s.second] + i.first;
q.push({-dist[coordinate.first][coordinate.second], coordinate});
}
}
}
if(dist[n - 1][m - 1] != mod)
cout << dist[n - 1][m - 1] << endl;
else
cout << -1 << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
0 ms |
332 KB |
Output is correct |
35 |
Correct |
7 ms |
460 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
8 ms |
548 KB |
Output is correct |
38 |
Correct |
1 ms |
972 KB |
Output is correct |
39 |
Correct |
91 ms |
2092 KB |
Output is correct |
40 |
Correct |
76 ms |
2012 KB |
Output is correct |
41 |
Correct |
5 ms |
1740 KB |
Output is correct |
42 |
Correct |
77 ms |
2092 KB |
Output is correct |
43 |
Correct |
113 ms |
5060 KB |
Output is correct |
44 |
Correct |
4 ms |
1764 KB |
Output is correct |