dfs迷宫寻路需用visited数组防重复访问和死循环；用方向数组遍历四邻，越界、撞墙或已访问则跳过；到达终点时将坐标加入path，递归回溯构建完整路径。
DFS 实现迷宫寻路：用递归栈模拟“撞墙回退”
迷宫寻路本质是图的遍历问题，C++ 中 DFS 最自然的写法是递归——每步尝试上下左右，失败就自动回溯。关键不是“怎么写递归”，而是**怎么避免重复访问和死循环**。
- 必须用
visited二维布尔数组（或直接修改原迷宫标记为障碍），否则会反复进入同一格子 - 方向数组建议用
vector<pair>> dirs = {{-1,0},{0,1},{1,0},{0,-1}};</pair>，比硬写四次 if 更易维护 - 递归终止条件除了到达终点，还要检查坐标是否越界、是否为墙（如值为
1）或已访问 - 若需返回路径，不能只靠递归返回 bool，得用引用传入
vector<pair>>& path</pair>，在成功时逐层 push_back 当前点
void dfs(vector<vector<int>>& maze, int x, int y, vector<vector<bool>>& visited,
const pair<int,int>& end, vector<pair<int,int>>& path) {
if (x == end.first && y == end.second) {
path.push_back({x, y});
return;
}
visited[x][y] = true;
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < maze.size() && ny >= 0 && ny < maze[0].size() &&
!visited[nx][ny] && maze[nx][ny] == 0) {
dfs(maze, nx, ny, visited, end, path);
if (!path.empty()) { // 找到路径就提前退出
path.push_back({x, y});
return;
}
}
}
}BFS 实现迷宫寻路：用队列保证“最短路径”
BFS 天然适合求无权图最短路径，迷宫中每步代价相同，所以 BFS 第一次抵达终点时，路径长度一定最短。但要注意：**BFS 不回溯，必须显式记录每个节点的前驱**，否则无法还原路径。
- 用
queue<pair>></pair>存待扩展坐标，用vector<vector>>> prev</vector>记录每个位置的上一步（初始化为{-1,-1}） - 遇到终点后，从终点沿
prev往回跳，用 stack 或 reverse 存路径 - 不推荐用
map<pair>, pair<int>></int></pair>存前驱——哈希开销大，二维 vector 随机访问更快 - 如果迷宫很大且内存敏感，可改用一维索引（
y * width + x）压缩空间
vector<pair<int,int>> bfs(vector<vector<int>>& maze, pair<int,int> start, pair<int,int> end) {
int n = maze.size(), m = maze[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
vector<vector<pair<int,int>>> prev(n, vector<pair<int,int>>(m, {-1,-1}));
queue<pair<int,int>> q;
q.push(start);
visited[start.first][start.second] = true;
<pre class='brush:php;toolbar:false;'>while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second) break;
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!visited[nx][ny] && maze[nx][ny] == 0) {
visited[nx][ny] = true;
prev[nx][ny] = {x, y};
q.push({nx, ny});
}
}
}
// 重构路径
vector<pair<int,int>> path;
for (auto p = end; p != make_pair(-1,-1); p = prev[p.first][p.second]) {
path.push_back(p);
}
reverse(path.begin(), path.end());
return path;}
DFS vs BFS：选哪个？看你要什么
两者时间复杂度都是 O(V+E)，但实际表现差异明显。不是“哪个更好”，而是“哪个更合适”。
立即学习“C++免费学习笔记（深入）”；
- 要**任意一条可行路径**，且迷宫稀疏（死路少）、终点离起点近 → DFS 通常更快，栈空间小，代码简洁
- 要**最短路径**，或迷宫里有大量分支/环 → 必须 BFS；DFS 可能先找到一条绕远的路径，还得继续搜完所有分支才能确认最短
- 内存限制严苛 → DFS 递归深度可能爆栈（比如 1000×1000 迷宫），此时需手动用 stack 模拟 DFS，或改用迭代加深（IDFS）
- 想边搜索边渲染动画效果 → BFS 天然按层展开，每轮 queue 中的点就是当前“波前”，视觉上更直观
容易被忽略的坑：边界、输入格式与性能陷阱
算法逻辑正确，不代表程序能过所有测试。真实场景下，这些细节常导致 WA 或 TLE。
- 迷宫输入可能是字符（
'0'和'1'），别直接当整数用；用grid[i][j] == '0'判断通路 - 起点/终点坐标可能给反（行/列顺序），务必确认题目约定是
[row][col]还是[x][y] - DFS 递归太深时，Linux 默认栈只有 8MB，本地测试没问题，OJ 上可能 SIGSEGV；加编译选项
-Wl,--stack,33554432（32MB）或改非递归 - BFS 中重复入队是常见错误：必须在入队前设
visited=true，而不是出队时才设，否则同一格子可能被多个邻居同时加入队列
DFS 和 BFS 在迷宫里看起来只是“栈换队列”，但路径性质、内存行为、调试难度完全不同。动手前先问自己：我要的是“有解就行”，还是“必须最短”？这个判断比写对循环体更重要。
