C++ 基于BFS算法的走迷宫自动寻路的实现

前言

走迷宫是广度优先搜索（breadth-first search, BFS）最直观的应用：网格中有些格子可以走、有些是墙，从起点出发，每次可以向上下左右移动一格，求到终点的最短路径。BFS 按「离起点的步数」一层一层扩展，第一次到达某个格子时走过的步数一定最少。

常见误解有四个。第一，用深度优先搜索（DFS）找路，能走通就返回，但找到的不一定最短。第二，把「访问标记」放在出队时而不是入队时，同一个格子会被多次加入队列，路径记录也会被覆盖。第三，只记录「来过的方向」而不记录完整父节点，回溯时拼不出路径。第四，把 BFS 当成有权图的最短路算法；BFS 只适用于每条边代价相同的图，边权不同要用 Dijkstra 等算法。

本文用二维网格建模，给出 BFS 求最短距离、父节点表还原路径的完整实现，并说明 4 邻域与 8 邻域的区别。代码以 C++17 为准，只使用标准库。

一、BFS 为什么能得到最短路径

BFS 使用队列，先入先出。把起点看作第 0 层，所有与起点相邻的可走格子是第 1 层，再往外是第 2 层，依此类推。队列的顺序保证：第 k 层的节点全部处理完之前，不会处理第 k+1 层的节点。

在边权都为 1 的图里，「路径长度」就是边的条数。第一次访问某个节点时，BFS 一定是从离起点最近的方向到达的；如果存在更短的路径，那条路径上的节点会先被访问，当前节点就会更早入队。因此，节点第一次入队时记录的层数就是最短距离。

这个性质依赖两个前提：所有边的代价相同；访问标记在入队时就设置。若在出队时才标记，同一个节点可能被不同层重复入队，虽然最终距离可能仍对，但队列膨胀、父节点被后来的路径覆盖，路径还原就会出错。

二、网格、方向与状态

网格用std::vector<std::vector<int>>表示，0 表示可走，1 表示墙。起点和终点用行列坐标(r, c)表示。4 邻域的方向数组是：

dr: -1 1 0 0
dc: 0 0 -1 1

每个候选位置要依次检查：是否在网格内、是否是墙、是否已经访问。三个条件都满足才入队。顺序不能反：越界访问是未定义行为（undefined behavior, UB），必须先判界再访问grid[nr][nc]。

距离表dist初始化为 -1，表示未访问；起点的dist为 0。父节点表parent保存「当前格子是从哪个格子走来的」，起点没有父节点。也可以用一维数组把坐标编码成r * cols + c，省掉一层 vector，但二维写法更直观，本文用二维。

如果起点或终点本身是墙，直接判定不可达，不要进入搜索。起点等于终点时，路径只包含起点，距离为 0，这个边界要单独想清楚，否则回溯循环可能多走一步或死循环。

三、搜索与路径还原

搜索过程：

1. 
   
2. 起点入队，dist设为 0。
3. 
   
4. 队列非空时取队头。若队头就是终点，可以提前结束（距离已经确定）。
5. 
   
6. 否则枚举四个方向，对每个合法且未访问的邻居，设置dist = dist[cur] + 1、parent = cur，然后入队。
7. 
   
8. 队列空了仍未到达终点，说明不可达。
9. 
   

路径还原从终点开始，沿着parent一路走到起点，把经过的格子收集起来，最后反转。由于parent是在入队时设置的，每个格子只对应一条「首次到达」的路径，回溯不会分叉。

这里有一个容易忽略的细节：路径数组里是否包含起点和终点。本文的实现两者都包含，因此路径长度（格子数）比步数多 1；若题目要的是步数，输出path.size() - 1。把「节点数」和「边数」混为一谈，是路径题常见的差一错误。

四、完整实现与变体

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

struct Point {
int r = 0;
int c = 0;
};

bool bfs(const std::vector<std::vector<int>>& grid, Point start, Point goal,
std::vector<Point>& path) {
const int rows = static_cast<int>(grid.size());
if (rows == 0) return false;
const int cols = static_cast<int>(grid[0].size());

auto inside = [rows, cols](int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
};

if (!inside(start.r, start.c) || !inside(goal.r, goal.c)) return false;
if (grid[start.r][start.c] != 0 || grid[goal.r][goal.c] != 0) return false;

const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

std::vector<std::vector<int>> dist(
rows, std::vector<int>(cols, -1));
std::vector<std::vector<Point>> parent(
rows, std::vector<Point>(cols, Point{-1, -1}));

std::queue<Point> q;
dist[start.r][start.c] = 0;
q.push(start);

while (!q.empty()) {
const Point cur = q.front();
q.pop();

if (cur.r == goal.r && cur.c == goal.c) {
break;
}

for (int k = 0; k < 4; ++k) {
const int nr = cur.r + DR[k];
const int nc = cur.c + DC[k];
if (!inside(nr, nc)) continue;
if (grid[nr][nc] != 0) continue;
if (dist[nr][nc] != -1) continue;

dist[nr][nc] = dist[cur.r][cur.c] + 1;
parent[nr][nc] = cur;
q.push(Point{nr, nc});
}
}

if (dist[goal.r][goal.c] == -1) {
return false;
}

path.clear();
Point cur = goal;
while (!(cur.r == start.r && cur.c == start.c)) {
path.push_back(cur);
cur = parent[cur.r][cur.c];
}
path.push_back(start);
std::reverse(path.begin(), path.end());
return true;
}

int main() {
const std::vector<std::vector<int>> maze = {
{0, 0, 0, 0, 1},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0},
};

std::vector<Point> path;
if (bfs(maze, Point{0, 0}, Point{4, 4}, path)) {
std::cout << "steps: " << path.size() - 1 << '\n';
for (const Point& p : path) {
std::cout << '(' << p.r << ", " << p.c << ") ";
}
std::cout << '\n';
} else {
std::cout << "unreachable\n";
}
return 0;
}

这个迷宫从(0,0)到(4,4)是可走的，输出会给出步数和一条最短路径；路径可能不唯一，因为同一层可能有多个前驱，BFS 选择的是「最早把它入队」的那个，具体取决于方向数组的枚举顺序。不要假定某一条特定路径是唯一答案。

8 邻域与带权变体

如果允许斜着走，把方向数组换成 8 组增量即可，BFS 仍然按「边数」分层，得到的是最少移动次数。但斜走一步的几何距离是根号 2，而直走一步是 1；若题目要求的是欧几里得距离最短，BFS 的「步数最少」不等于「长度最短」，需要换成考虑边权的算法。这个区别在游戏寻路里很重要，不能把「步数」和「距离」混用。

若每条边的代价不同（例如不同地形有不同的移动代价），BFS 不再适用。边权非负时用 Dijkstra，边权只有 0 和 1 时可以用 0-1 BFS（双端队列）。这些算法的共同点是：都维护「当前已知最短距离」，只是取最小值的结构不同。

常见坑点

1. 用 DFS 求最短路

❌ 递归找到一条通路就返回，认为它就是最短的。

✅ 无权图最短路用 BFS，按层扩展，第一次到达即最短。

2. 出队时才标记访问

❌ 入队不标记，弹出时才把dist设为已访问，同一格被多次入队。

✅ 入队时立刻设置dist和parent，保证每个格子只入队一次。

3. 不判边界就访问数组

❌ 先写grid[nr][nc]，再判断nr、nc是否越界。

✅ 先inside(nr, nc)，利用短路求值再访问。

4. 忘记检查起点或终点是墙

❌ 直接开始搜索，终点为墙时永远不可达，却仍做完整 BFS。

✅ 搜索前检查两格的grid值，非 0 直接返回 false。

5. 无路径时仍回溯

❌dist为 -1 还从终点沿parent走，父节点是(-1,-1)，越界。

✅ 先判断dist[goal] == -1，再进入路径还原。

6. 入队时不记录父节点

❌ 只更新距离，路径还原时不知道从哪来。

✅ 入队时同时写parent[nr][nc] = cur。

7. 方向数组与邻域不匹配

❌ 声明 8 个方向，循环却只跑 4 次；或反之。

✅ 方向数组长度与循环上界一致，4 邻域与 8 邻域分开写。

8. 把 BFS 用于带权图

❌ 边权不为 1 时仍用普通队列，得到的不一定是最短距离。

✅ 非负边权用 Dijkstra，0/1 边权用 0-1 BFS。

总结

BFS 走迷宫的核心是「一层一层」：队列保证层序，入队标记保证每格只处理一次，父节点表保证路径可还原。把这三件事写对，剩下的只是方向数组和边界判断，不会在「最短路」这个目标上偏离。