Problem F: 迷宫
📝 题目描述
迷宫模板题,要求记录路径
🔑 算法模块
bfs
💡 思路分析
题目要求最短路径,深度优先在搜索过程中会回溯,将已访问打下的标记重置,而广度优先不需要回溯,所以深度优先的复杂度显然高于广度优先,我们使用 \(BFS\) 算法。
先将起点入队,再依次遍历当前点的四个方向,同时记录痕迹。第一次遍历到某点时一定是最短路,所以我们可以在这个点记录来时的方向。同理,第一次遍历到 \(B\) 点时也是最短路,我们可以直接停止搜索工作了,然后沿着来时的痕迹记录路线
🖥️ 代码实现
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 | #include <bits/stdc++.h>
using namespace std;
#define int long long
//四个移动方向及其对应的操作字母
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
char dir[] = {'D', 'R', 'U', 'L'};
void solve() {
int n, m;
cin >> n >> m;
//a数组记录输入的地图,pre数组记录到达该点的前一次操作
vector<vector<char>> a(n, vector<char>(m)), pre(n, vector<char>(m));
//b数组记录访问
vector<vector<bool>> b(n, vector<bool>(m, false));
//q队列执行BFS
//为什么要用队列呢?
//队列的性质是先进先出
//也就是说先拿出来的进队的时间早
//进的早就意味先访问
//先访问就意味着离起点近
//把队首元素拿出,再把他能走到的点推入队尾
//可以想一下,新加进去的元素离得一定比原队列中所有的元素远,或者距离一样,反正不可能更近
//我们就是用这种性质来维护最短路嘟
queue<pair<int, int>> q;
//记录A和B的位置
int ax = -1, ay = -1, bx = -1, by = -1;
//处理输入
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; i++) {
cin >> a[i][j];
if (a[i][j] == 'A') {
ax = i;
ay = j;
b[i][j] = true;
q.push({i, j});
} else if (a[i][j] == 'B') {
bx = i;
by = j;
}
}
}
//ok来标记是否已搜索到终点
bool ok = false;
//开搜!!!
while (!q.empty() && !ok) {
//拿出队首元素
auto [x, y] = q.front();
q.pop();
//四个移动方向
for (int i = 0; i < 4; i++) {
//下一个位置
int nx = x + dx[i];
int ny = y + dy[i];
//下一个位置是否在图内,是否可以行走,是否已被访问
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !b[nx][ny] && a[nx][ny] != '#') {
//打上已访问标记
b[nx][ny] = true;
//在下一个点上,记录从此处到下一点的操作
//如果从别的点也能过来咋办捏
//就记录第一次就够了,第一次一定是最短滴
pre[nx][ny] = dir[i];
//处理完将下一个点入队
q.push({nx, ny});
//如果走到了终点就不搜了
if (nx == bx && ny == by) {
ok = true;
break;
}
}
}
}
//没搜到QAQ
if (!ok) {
cout << "NO\n";
return;
}
//从B点沿着我们之前的记录回溯到A
string s;
int x = bx, y = by;
while (x != ax || y != ay) {
char d = pre[x][y];
s += d;
if (d == 'D') x -= 1;
else if (d == 'R') y -= 1;
else if (d == 'U') x += 1;
else if (d == 'L') y += 1;
}
//居然是反着的QAQ~
//嗬!乾坤翻转!!!
reverse(s.begin(), s.end());
cout << "YES\n";
cout << s.size() << "\n";
cout << s << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
|
⏱️ 复杂度分析
📚 拓展