#include<bits/stdc++.h>
using namespace std;
enum class Location {
Upper = 1,
Left = 2,
Lower = 3,
Right = 4
};
enum class Orientation {
X = -1, //empty
S = 1, //south
E = 2, //east
N = 3, //north
W = 4 //west
};
struct Coord {
int x, y;
Coord(int a = 0, int b = 0) : x(a), y(b) {};
bool operator<(const Coord &other) const {
if (x < other.x) return true;
else if (x > other.x) return false;
else return y < other.y;
}
};
struct Cell {
Coord coord;
Orientation orientation;
Cell(Coord a = Coord(), Orientation b = Orientation::X) : coord(a), orientation(b) {};
};
struct Neighbor {
Coord coord;
int distance;
Neighbor(Coord a = Coord(), int b = 0) : coord(a), distance(b) {};
};
vector<vector<Cell>> grid;
int M, N;
vector<vector<int>> dist;
Orientation getOrientation (char charorientation) {
switch (charorientation) {
case 'S':
return Orientation::S;
case 'E':
return Orientation::E;
case 'N':
return Orientation::N;
case 'W':
return Orientation::W;
default:
return Orientation::X;
}
}
int distToNeigh(Location location, Orientation orientation) {
return (((int)orientation - (int)location)+4)%4;
}
void checkNeigh(Coord curr, Location neighLocation, vector<Neighbor> &result) {
bool exists;
Coord neighCoord;
switch(neighLocation) {
case Location::Upper:
exists = (curr.y > 0);
neighCoord = Coord(curr.x, curr.y - 1);
break;
case Location::Left:
exists = (curr.x > 0);
neighCoord = Coord(curr.x - 1, curr.y);
break;
case Location::Lower:
exists = (curr.y < M - 1);
neighCoord = Coord(curr.x, curr.y + 1);
break;
case Location::Right:
exists = (curr.x < N - 1);
neighCoord = Coord(curr.x + 1, curr.y);
break;
default:
exists = false;
break;
}
if(exists) {
Cell neighCell = grid[neighCoord.x][neighCoord.y];
if(neighCell.orientation != Orientation::X) {
result.push_back(Neighbor(neighCoord, distToNeigh(neighLocation, neighCell.orientation)));
}
}
}
vector<Neighbor> getNeigh(Coord curr) {
vector<Neighbor> result;
for(int i = 1; i <= 4; i++) {
checkNeigh(curr, (Location)i, result);
}
return result;
}
void dijkastra() {
dist[N-1][M-1] = 0;
vector<vector<bool>> done (N, vector<bool>(M));
priority_queue<pair<int, Coord>> q;
q.push({0, Coord(N-1, M-1)});
while(!q.empty()){
Coord curr = q.top().second; q.pop();
if(!done[curr.x][curr.y]) {
done[curr.x][curr.y] = true;
vector<Neighbor> neighs = getNeigh(curr);
for(Neighbor neigh : neighs) {
if(dist[curr.x][curr.y] + neigh.distance < dist[neigh.coord.x][neigh.coord.y] || dist[neigh.coord.x][neigh.coord.y] == -1) {
dist[neigh.coord.x][neigh.coord.y] = dist[curr.x][curr.y] + neigh.distance;
q.push({-dist[neigh.coord.x][neigh.coord.y], neigh.coord});
}
}
}
}
}
int main() {
cin >> M >> N;
grid.resize(N, vector<Cell>(M));
dist.resize(N, vector<int>(M, -1));
for(int y = 0; y < M; y++) {
string row; cin >> row;
for(int x = 0; x < N; x++) {
grid[x][y] = Cell(Coord(x, y), getOrientation(row[x]));
}
}
dijkastra();
cout << dist[0][0] << "\n";
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 |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
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 |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
404 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 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 |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
1 ms |
404 KB |
Output is correct |
24 |
Correct |
0 ms |
256 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
0 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
692 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
14 ms |
768 KB |
Output is correct |
38 |
Correct |
17 ms |
1024 KB |
Output is correct |
39 |
Correct |
112 ms |
4608 KB |
Output is correct |
40 |
Correct |
105 ms |
4608 KB |
Output is correct |
41 |
Correct |
97 ms |
4736 KB |
Output is correct |
42 |
Correct |
98 ms |
4680 KB |
Output is correct |
43 |
Correct |
158 ms |
7784 KB |
Output is correct |
44 |
Correct |
97 ms |
4608 KB |
Output is correct |