前言迷宫问题包含两个独立的部分生成一棵连通且无环的通道结构以及求解从入口到出口的一条路径。很多人把它们混在一起写一个 DFS 一边挖墙一边找路结果生成的迷宫要么有环可以绕圈要么不连通出口根本到不了。另一个常见误解是迷宫必须用二维字符数组画出来才算实现。实际上生成与求解都只依赖格子之间的连通关系渲染只是最后一步。把数据结构和显示分开生成算法可以换成 Prim、Kruskal 而求解代码一行不改显示也可以从字符画换成图形界面。本文用每个格子记录四面墙的表示法实现经典的随机深度优先递归回溯生成算法保证生成的迷宫是一棵生成树——任意两格之间恰好有一条路径再用广度优先搜索求最短路径。全部代码以 C17 为基准只用标准库。一、迷宫怎么表示有两种等价表示选哪种只影响代码手感表示法数据结构优点缺点格子带墙每格存上下左右四面墙的布尔值挖墙操作直观渲染自然相邻格子的墙要同步修改墙格网格(2h1) × (2w1)的字符网格渲染简单直接打印通道与墙的坐标要换算本文用第一种。四个方向按固定顺序编号0上、1右、2下、3左。这个顺序有个便利性质方向d的反方向是d ^ 2因为 0 与 2 互补、1 与 3 互补异或 2 恰好互换。// 适用于 C17struct Cell {bool wall[4] {true, true, true, true}; // 上、右、下、左true 表示有墙};用一个一维std::vectorCell存所有格子行列下标通过r * cols c计算。一维存储的好处是缓存连续、索引唯一BFS 的访问标记也可以直接用同样大小的vector。二、生成随机深度优先递归回溯算法描述很短从任意格子出发标记为已访问。在当前格子随机选一个未访问的邻格打通两格之间的墙移动到邻格压栈。如果四个邻格都已访问弹栈回到上一个格子。栈空时结束。每个格子只被访问一次每次访问恰好打通一条墙所以最终打通rows*cols - 1条边构成一棵生成树连通且无环。这也是为什么这样生成的迷宫从任何格子都能到达任何格子而且路径唯一。递归写法最直观但深度等于格子数大迷宫会耗尽调用栈。下面用显式std::stack这里用vector充当栈改成迭代深度不再是问题。// 适用于 C17#include algorithm#include cstddef#include random#include stdexcept#include vectorclass Maze {public:Maze(int rows, int cols, unsigned seed): rows_(rows), cols_(cols),cells_(static_caststd::size_t(rows) * static_caststd::size_t(cols)) {if (rows 0 || cols 0) throw std::invalid_argument(bad size);generate(seed);}int rows() const { return rows_; }int cols() const { return cols_; }private:void generate(unsigned seed) {static const int dr[4] {-1, 0, 1, 0}; // 上、右、下、左static const int dc[4] {0, 1, 0, -1};std::mt19937 rng(seed);std::vectorchar visited(cells_.size(), 0);std::vectorint stack;std::vectorint order {0, 1, 2, 3};stack.push_back(0);visited[0] 1;while (!stack.empty()) {int id stack.back();int r id / cols_;int c id % cols_;std::shuffle(order.begin(), order.end(), rng); // 每步重新打乱方向bool carved false;for (int k 0; k 4; k) {int d order[k];int nr r dr[d];int nc c dc[d];if (nr 0 || nr rows_ || nc 0 || nc cols_) continue;int nid nr * cols_ nc;if (visited[static_caststd::size_t(nid)]) continue;at(r, c).wall[d] false; // 打通当前格这一侧at(nr, nc).wall[d ^ 2] false; // 打通邻格相反的一侧visited[static_caststd::size_t(nid)] 1;stack.push_back(nid);carved true;break; // 每次只前进一格}if (!carved) stack.pop_back(); // 四面都走过了回溯}}Cell at(int r, int c) {return cells_[static_caststd::size_t(r) * static_caststd::size_t(cols_) static_caststd::size_t(c)];}const Cell at(int r, int c) const {return cells_[static_caststd::size_t(r) * static_caststd::size_t(cols_) static_caststd::size_t(c)];}int rows_;int cols_;std::vectorCell cells_;};这里有两处容易写错。一是只打通了一侧的墙格子 A 与 B 相邻必须同时把 A 的右墙和 B 的左墙置为false只改一边会出现从 A 能过去、从 B 回不来的诡异结构。二是d ^ 2必须与方向表的顺序严格对应顺序改成上右下左以外的排列异或就不再是反方向。std::mt19937是标准库的梅森旋转引擎配合固定种子可以复现同一张迷宫便于调试和写测试。不要用std::rand()它的实现质量与平台相关且全局状态容易被别处调用打乱。三、求解广度优先搜索边权都是 1走一格算一步时BFS 首次到达终点时的路径就是最短路径。用一个prev数组记录每个格子是从哪个格子走来的到达终点后沿prev回溯即可。下面的solve是Maze的成员函数为节省篇幅单独列出实际写在类定义内部。// 适用于 C17#include queue#include utilitystd::vectorstd::pairint, int solve() const {static const int dr[4] {-1, 0, 1, 0};static const int dc[4] {0, 1, 0, -1};const int total rows_ * cols_;std::vectorint prev(static_caststd::size_t(total), -1);std::queueint q;prev[0] 0; // 起点自指作为回溯终止标记q.push(0);while (!q.empty()) {int id q.front();q.pop();int r id / cols_;int c id % cols_;if (r rows_ - 1 c cols_ - 1) break;for (int d 0; d 4; d) {if (at(r, c).wall[d]) continue; // 有墙走不通int nr r dr[d];int nc c dc[d];if (nr 0 || nr rows_ || nc 0 || nc cols_) continue;int nid nr * cols_ nc;if (prev[static_caststd::size_t(nid)] ! -1) continue; // 已访问prev[static_caststd::size_t(nid)] id;q.push(nid);}}std::vectorstd::pairint, int path;int goal total - 1;if (prev[static_caststd::size_t(goal)] -1) return path; // 不可达for (int cur goal; cur ! 0; cur prev[static_caststd::size_t(cur)]) {path.emplace_back(cur / cols_, cur % cols_);}path.emplace_back(0, 0);std::reverse(path.begin(), path.end());return path;}把prev当访问标记用可以省掉一个visited数组-1表示没到过非负表示前驱。注意起点的prev[0]也必须是有效值否则回溯时cur ! 0的判断会在起点处停不下来。如果迷宫不是树而是有环的图BFS 依然正确DFS 也能找到一条路但不保证最短。这是面试里常见的追问点。四、渲染与主程序渲染时按行输出先画顶部边框然后对每一行输出左墙 每格的右侧墙再输出底部墙。print同样写在Maze类定义内部下面的main负责驱动。// 适用于 C17#include iostreamvoid print() const {std::cout ;for (int c 0; c cols_; c) std::cout --;std::cout \n;for (int r 0; r rows_; r) {std::cout |;for (int c 0; c cols_; c) {std::cout ;std::cout (at(r, c).wall[1] ? | : );}std::cout \n ;for (int c 0; c cols_; c) {std::cout (at(r, c).wall[2] ? -- : ) ;}std::cout \n;}}int main() {Maze maze(10, 15, 2024u);maze.print();auto path maze.solve();std::cout steps: path.size() \n;for (const auto p : path) {std::cout ( p.first , p.second ) ;}std::cout \n;}生成与求解的复杂度都是O(rows * cols)每个格子入队一次每条墙检查常数次。空间同样是一个格子一份记录与格子总数成正比。常见坑点1. 只打通一侧的墙// ❌ 从 A 能进 B从 B 回不到 Aat(r, c).wall[d] false;// ✅ 两侧同时打通at(r, c).wall[d] false;at(nr, nc).wall[d ^ 2] false;2. 递归生成导致栈溢出// ❌ 深度等于格子数大迷宫会耗尽调用栈void dfs(int r, int c) { /* 递归四个方向 */ }// ✅ 用显式栈迭代std::vectorint stack;stack.push_back(0);3. BFS 不标记访问重复入队// ❌ 同一格子反复入队队列爆炸甚至死循环q.push(nid);// ✅ 入队前确认未访问并立刻标记if (prev[nid] ! -1) continue;prev[nid] id;q.push(nid);4. 用 DFS 求最短路// ❌ DFS 先找到的路径不一定最短// ✅ 边权为 1 时用 BFSstd::queueint q;5. 随机数用rand()且不播种// ❌ 每次运行都是同一张迷宫且分布质量依赖实现int d std::rand() % 4;// ✅ 用 random 的引擎种子显式传入std::mt19937 rng(seed);std::shuffle(order.begin(), order.end(), rng);6. 行列与下标换算写反// ❌ rows 与 cols 用错越界或错位int r id % rows_;// ✅ 一维下标与二维坐标严格对应int r id / cols_;int c id % cols_;7. 只生成不封边界// ❌ 边界格子的外墙被误打通路径能走出迷宫// ✅ 生成时只处理相邻且在界内的邻格if (nr 0 || nr rows_ || nc 0 || nc cols_) continue;总结环节方法保证表示每格四面墙 一维数组索引唯一、缓存友好生成随机 DFS显式栈连通、无环、恰好一棵生成树求解BFS 前驱数组边权为 1 时的最短路径渲染逐行输出墙与通道与内部结构解耦复杂度时间与空间均为O(rows*cols)与格子数线性相关迷宫的关键在于把生成和求解当成两件事生成负责构造一棵树求解负责在这棵树上找路。只要表示法统一墙在格子上、方向顺序固定、反方向用异或求得两个算法可以各自替换而互不影响。