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)，但实际表现差异明显。不是“哪个更好”，而是“哪个更合适”。

							

								
								

									Procys
									
AI驱动的发票数据处理
								
								下载 
							
						
立即学习“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 在迷宫里看起来只是“栈换队列”，但路径性质、内存行为、调试难度完全不同。动手前先问自己：我要的是“有解就行”，还是“必须最短”？这个判断比写对循环体更重要。