前言迷宫问题通常这样描述一个R × C的网格0表示可以走的通道1表示墙壁从起点出发每次可以向上、下、左、右移动一格求是否能到达终点、最少需要多少步、或者输出一条可行路径。它是搜索算法最直观的练兵场。初学者最容易混淆的是「找一条路径」和「找最短路径」前者用深度优先搜索depth-first search, DFS加回溯即可后者在无权网格上应当用广度优先搜索breadth-first search, BFS。用 DFS 找到的第一条路径不一定最短用 BFS 第一次到达终点时经过的步数一定最短。另一个常见错误是访问标记的处理。DFS 回溯时如果找到一条走不通的分支应该把该格子的「已访问」标记撤销否则其他分支可能被错误地封锁但如果只是判断「是否能到达」不撤销也不会影响正确性只是会少探索一些路径。BFS 则相反标记应当在入队时设置并且不需要撤销。本文给出 DFS 找路径和 BFS 求最短步数两种实现并说明它们各自的适用场景。代码以 C17 为基准。一、迷宫建模用std::vectorstd::vectorint表示迷宫行列从 0 开始。方向数组是常见写法// 适用于 C17const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};四个方向分别对应上、下、左、右。用两个数组而不是四段if可以让遍历方向的代码更短也不容易漏掉某个方向。边界条件新坐标必须满足0 nr R、0 nc C。maze[nr][nc] 0。该格子不在当前路径上DFS或未被访问BFS。二、DFS 找一条路径DFS 的思路是「一条路走到黑走不通就退回上一个格子换一个方向」。递归函数返回bool表示从当前格子出发能否到达终点。// 适用于 C17#include vectorstruct Point {int r;int c;};bool dfs(std::vectorstd::vectorint maze,int r, int c, Point target,std::vectorstd::vectorbool visited,std::vectorPoint path) {const int rows static_castint(maze.size());const int cols static_castint(maze[0].size());if (r 0 || r rows || c 0 || c cols) return false;if (maze[r][c] 1) return false;if (visited[r][c]) return false;visited[r][c] true;path.push_back({r, c});if (r target.r c target.c) return true;const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};for (int d 0; d 4; d) {if (dfs(maze, r dr[d], c dc[d], target, visited, path)) {return true;}}path.pop_back();visited[r][c] false;return false;}关键点visited[r][c] true在进入格子时设置visited[r][c] false在四个方向都失败后撤销。这样visited表示的是「当前路径上已经走过的格子」而不是「整个搜索过程中访问过的格子」。找到终点时直接返回true不再撤销标记也不再pop_back。这样path里保留的是从起点到终点的完整路径调用方可以直接使用。如果四个方向都失败说明当前格子不在任何可行路径上把它从path中弹出、标记撤销返回false让上一层换方向。递归深度最多等于路径长度最坏是R × C。对很大的迷宫递归可能栈溢出需要改成显式栈的迭代版本。为什么必须撤销visited考虑一个「T」形路口从左边进来先尝试向上走发现是死胡同如果向上的格子仍被标记为已访问那么从右边绕回来时就不能再经过它可能漏掉一条需要「回头再走另一条分支」的路径。撤销标记让搜索回到进入前的状态保证所有简单路径都能被探索到。三、BFS 求最短步数BFS 用队列按层扩展第一次到达某个格子时的步数就是最短步数。核心代码// 适用于 C17#include queue#include vectorint bfsDistance(const std::vectorstd::vectorint maze,Point start, Point target) {const int rows static_castint(maze.size());const int cols static_castint(maze[0].size());std::vectorstd::vectorint dist(rows, std::vectorint(cols, -1));std::queuePoint q;dist[start.r][start.c] 0;q.push(start);const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};while (!q.empty()) {const Point cur q.front();q.pop();if (cur.r target.r cur.c target.c) {return dist[cur.r][cur.c];}for (int d 0; d 4; d) {const int nr cur.r dr[d];const int nc cur.c dc[d];if (nr 0 || nr rows || nc 0 || nc cols) continue;if (maze[nr][nc] 1 || dist[nr][nc] ! -1) continue;dist[nr][nc] dist[cur.r][cur.c] 1;q.push({nr, nc});}}return -1;}dist同时承担「是否访问」和「距离」两个职责初始化为 -1。入队前就设置距离保证每个格子最多入队一次。如果起点或终点本身是墙这段代码仍会把起点入队没有检查maze[start]需要在调用前判断或者在函数开头加检查// 适用于 C17if (maze[start.r][start.c] 1 || maze[target.r][target.c] 1) {return -1;}四、两种方法的对比维度DFS 回溯BFS数据结构递归栈队列找到的路径任意一条可行路径最短路径无权图时间复杂度O(R·C)每个格子最多访问一次O(R·C)空间O(R·C) 最坏递归深度O(R·C) 队列与距离数组能否枚举所有路径能不提前返回不适合能否求最短步数不能直接保证能适用找一条路、连通性、枚举最短步数、最少操作DFS 的时间复杂度也是 O(R·C)因为visited保证每个格子在一条路径上只被访问一次但「撤销标记」意味着同一个格子可能在不同的路径分支中被多次进入最坏情况下退化为指数级比如大量分叉的迷宫。严格地说带撤销的 DFS 枚举的是所有简单路径路径数量可能是指数级的如果只判断「是否可达」不撤销标记或用全局 visited可以保证 O(R·C)。五、完整示例DFS 输出路径// 适用于 C17#include iostream#include vectorstruct Point {int r;int c;};bool dfs(std::vectorstd::vectorint maze,int r, int c, Point target,std::vectorstd::vectorbool visited,std::vectorPoint path) {const int rows static_castint(maze.size());const int cols static_castint(maze[0].size());if (r 0 || r rows || c 0 || c cols) return false;if (maze[r][c] 1) return false;if (visited[r][c]) return false;visited[r][c] true;path.push_back({r, c});if (r target.r c target.c) return true;const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};for (int d 0; d 4; d) {if (dfs(maze, r dr[d], c dc[d], target, visited, path)) {return true;}}path.pop_back();visited[r][c] false;return false;}int main() {std::vectorstd::vectorint maze{{0, 0, 0, 1, 0},{1, 1, 0, 1, 0},{0, 0, 0, 0, 0},{0, 1, 1, 1, 0},{0, 0, 0, 0, 0}};const int rows static_castint(maze.size());const int cols static_castint(maze[0].size());std::vectorstd::vectorbool visited(rows, std::vectorbool(cols, false));std::vectorPoint path;const Point start{0, 0};const Point target{4, 4};if (dfs(maze, start.r, start.c, target, visited, path)) {std::cout path length: path.size() \n;for (const Point p : path) {std::cout ( p.r , p.c ) ;}std::cout \n;} else {std::cout no path\n;}return 0;}这段代码只负责找一条路径不保证最短。对上面的迷宫沿最上方再向下的路径长度可能是 9 或 13取决于方向尝试的顺序如果要最短应该用 BFS并在 BFS 中记录parent还原路径。六、路径还原BFS 求最短路径时除了dist还需要一个parent数组记录每个格子是从哪里来的// 适用于 C17std::vectorstd::vectorPoint parent(rows, std::vectorPoint(cols, {-1, -1}));// 在扩展时parent[nr][nc] cur;// 到达终点后std::vectorPoint path;for (Point p target; !(p.r start.r p.c start.c); p parent[p.r][p.c]) {path.push_back(p);}path.push_back(start);std::reverse(path.begin(), path.end());parent的初值{-1, -1}不会被读到因为回溯在起点停止。std::reverse需要包含algorithm。常见坑点1. 认为 DFS 找到的路径最短❌ 用 DFS 输出路径后声称是最短路径。✅ DFS 只保证「一条可行路径」最短用 BFS或记录所有路径后取最短。2. 回溯时忘记撤销 visited❌visited[r][c] true;之后失败返回没有恢复。✅ 失败分支visited[r][c] false;并把当前格子从路径弹出。3. 找到终点后仍然撤销❌ 找到终点后继续pop_back返回的path不完整。✅ 找到后立即返回保留路径或者先保存路径副本再撤销。4. 越界检查在访问数组之后❌if (maze[r][c] 1)写在范围判断之前。✅ 先判断r、c是否在[0, rows)、[0, cols)内。5. BFS 出队时才标记❌q.pop(); if (visited[u]) continue; visited[u] true;✅ 入队前标记避免同一格子被多次加入队列。6. 起点或终点是墙❌ 直接把起点入队BFS 穿过墙或返回 0。✅ 函数开头检查两格的maze值。7. 递归深度过大❌ 对 1000×1000 的迷宫用递归 DFS。✅ 改成显式栈或限制规模BFS 没有递归深度问题。8. 方向数组写错❌dr和dc的组合把「左上」当成一个方向或漏掉某个方向。✅ 用{-1,1,0,0}和{0,0,-1,1}一一对应四个方向都要覆盖。总结需求算法关键点是否存在路径DFS 或 BFS访问标记输出一条路径DFS 回溯失败时撤销、弹出最短步数BFS入队时标记距离最短路径BFS parent反向追溯后反转枚举所有路径DFS 回溯找到后不立即返回迷宫问题的代码骨架很小难点在「状态什么时候设置、什么时候撤销」。DFS 的visited是路径级的失败要还原BFS 的dist是全局级的入队就固定。把这一点和「DFS 不保证最短」记清楚选择算法时就不会出错。