c++怎么实现迷宫寻路算法_c++ 深度优先搜索与广度优先搜索对比【实战】

DFS迷宫寻路需用visited数组防重复访问和死循环；用方向数组遍历四邻，越界、撞墙或已访问则跳过；到达终点时将坐标加入path，递归回溯构建完整路径。

DFS 实现迷宫寻路：用递归栈模拟“撞墙回退”

迷宫寻路本质是图的遍历问题，c++ 中 DFS 最自然的写法是递归——每步尝试上下左右，失败就自动回溯。关键不是“怎么写递归”，而是**怎么避免重复访问和死循环**。

• 必须用 visited 二维布尔数组（或直接修改原迷宫标记为障碍），否则会反复进入同一格子
• 方向数组建议用 vector> dirs = {{-1,0},{0,1},{1,0},{0,-1}};，比硬写四次 if 更易维护
• 递归终止条件除了到达终点，还要检查坐标是否越界、是否为墙（如值为 1）或已访问
• 若需返回路径，不能只靠递归返回 bool，得用引用传入 vector>& path，在成功时逐层 push_back 当前点

void dfs(vector>& maze, int x, int y, vector>& visited,          const pair& end, vector>& 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> 存待扩展坐标，用 vector>> prev 记录每个位置的上一步（初始化为 {-1,-1}）
• 遇到终点后，从终点沿 prev 往回跳，用 stack 或 reverse 存路径
• 不推荐用 map, pair> 存前驱——哈希开销大，二维 vector 随机访问更快
• 如果迷宫很大且内存敏感，可改用一维索引（y * width + x）压缩空间

vector> bfs(vector>& maze, pair start, pair end) {     int n = maze.size(), m = maze[0].size();     vector> visited(n, vector(m, false));     vector>> prev(n, vector>(m, {-1,-1}));     queue> q;     q.push(start);     visited[start.first][start.second] = true; 
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> 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)，但实际表现差异明显。不是“哪个更好”，而是“哪个更合适”。

要**任意一条可行路径**，且迷宫稀疏（死路少）、终点离起点近 → 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 在迷宫里看起来只是“栈换队列”，但路径性质、内存行为、调试难度完全不同。动手前先问自己：我要的是“有解就行”，还是“必须最短”？这个判断比写对循环体更重要。