-
Notifications
You must be signed in to change notification settings - Fork 1
/
2.Labyrinth.cpp
80 lines (67 loc) · 1.67 KB
/
2.Labyrinth.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Resource https://usaco.guide/solutions/cses-1193?lang=cpp
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
int n, m;
char A[1000][1000];
bool vis[1000][1000];
// previousStep stores the previous direction that we moved in to arrive that this cell
int previousStep[1000][1000];
// 0 = up, 1 = right, 2 = down, 3 = left
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
string stepDir = "URDL";
int main() {
cin >> n >> m;
queue<ii> q;
ii begin, end;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> A[i][j];
if (A[i][j] == 'A') {
begin = mp(i, j);
} else if (A[i][j] == 'B') {
end = mp(i, j);
}
}
}
// q.push(begin);
q.push(begin);
// vis[begin.f][begin.s] = true;
vis[begin.f][begin.s] = true;
while (!q.empty()) {
ii u = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
ii v = mp(u.f + dx[i], u.s + dy[i]);
if (v.f < 0 || v.f >= n || v.s < 0 || v.s >= m) continue;
if (A[v.f][v.s] == '#') continue;
if (vis[v.f][v.s]) continue;
vis[v.f][v.s] = true;
previousStep[v.f][v.s] = i;
q.push(v);
}
}
if (vis[end.f][end.s]) {
cout << "YES" << endl;
vector<int> steps;
while (end != begin) {
int p = previousStep[end.f][end.s];
steps.push_back(p);
// undo the previous step to get back to the previous square
// Notice how we subtract dx/dy, whereas we added dx/dy before
end = mp(end.f - dx[p], end.s - dy[p]);
}
reverse(steps.begin(), steps.end());
cout << steps.size() << endl;
for (char c : steps) {
cout << stepDir[c];
}
cout << endl;
} else {
cout << "NO" << endl;
}
return 0;
}