前言
迷宫问题包含两个独立的部分：生成一棵连通且无环的通道结构，以及求解从入口到出口的一条路径。很多人把它们混在一起，写一个 DFS 一边挖墙一边找路，结果生成的迷宫要么有环（可以绕圈），要么不连通（出口根本到不了）。
另一个常见误解是"迷宫必须用二维字符数组画出来才算实现"。实际上，生成与求解都只依赖格子之间的连通关系，渲染只是最后一步。把数据结构和显示分开，生成算法可以换成 Prim、Kruskal 而求解代码一行不改；显示也可以从字符画换成图形界面。
本文用"每个格子记录四面墙"的表示法，实现经典的随机深度优先（递归回溯）生成算法，保证生成的迷宫是一棵生成树——任意两格之间恰好有一条路径；再用广度优先搜索求最短路径。全部代码以 C++17 为基准，只用标准库。
一、迷宫怎么表示
有两种等价表示，选哪种只影响代码手感：
| 表示法 | 数据结构 | 优点 | 缺点 |
|---|
| 格子带墙 | 每格存上下左右四面墙的布尔值 | 挖墙操作直观，渲染自然 | 相邻格子的墙要同步修改 |
| 墙格网格 | (2h+1) × (2w+1)的字符网格 | 渲染简单，直接打印 | 通道与墙的坐标要换算 |
本文用第一种。四个方向按固定顺序编号：0=上、1=右、2=下、3=左。这个顺序有个便利性质：方向d的反方向是d ^ 2，因为 0 与 2 互补、1 与 3 互补，异或 2 恰好互换。
// 适用于 C++17
struct Cell {
bool wall[4] = {true, true, true, true}; // 上、右、下、左，true 表示有墙
};用一个一维std::vector<Cell>存所有格子，行列下标通过r * cols + c计算。一维存储的好处是缓存连续、索引唯一，BFS 的访问标记也可以直接用同样大小的vector。
二、生成：随机深度优先（递归回溯）
算法描述很短：
- 从任意格子出发，标记为已访问。
- 在当前格子随机选一个未访问的邻格，打通两格之间的墙，移动到邻格，压栈。
- 如果四个邻格都已访问，弹栈回到上一个格子。
- 栈空时结束。
每个格子只被访问一次，每次访问恰好打通一条墙，所以最终打通rows*cols - 1条边，构成一棵生成树：连通且无环。这也是为什么这样生成的迷宫从任何格子都能到达任何格子，而且路径唯一。
递归写法最直观，但深度等于格子数，大迷宫会耗尽调用栈。下面用显式std::stack（这里用vector充当栈）改成迭代，深度不再是问题。
// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <random>
#include <stdexcept>
#include <vector>
class Maze {
public:
Maze(int rows, int cols, unsigned seed)
: rows_(rows), cols_(cols),
cells_(static_cast<std::size_t>(rows) * static_cast<std::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::vector<char> visited(cells_.size(), 0);
std::vector<int> stack;
std::vector<int> 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_cast<std::size_t>(nid)]) continue;
at(r, c).wall[d] = false; // 打通当前格这一侧
at(nr, nc).wall[d ^ 2] = false; // 打通邻格相反的一侧
visited[static_cast<std::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_cast<std::size_t>(r) * static_cast<std::size_t>(cols_)
+ static_cast<std::size_t>(c)];
}
const Cell& at(int r, int c) const {
return cells_[static_cast<std::size_t>(r) * static_cast<std::size_t>(cols_)
+ static_cast<std::size_t>(c)];
}
int rows_;
int cols_;
std::vector<Cell> cells_;
};这里有两处容易写错。一是只打通了一侧的墙：格子 A 与 B 相邻，必须同时把 A 的右墙和 B 的左墙置为false，只改一边会出现"从 A 能过去、从 B 回不来"的诡异结构。二是d ^ 2必须与方向表的顺序严格对应，顺序改成"上右下左"以外的排列，异或就不再是反方向。
std::mt19937是标准库的梅森旋转引擎，配合固定种子可以复现同一张迷宫，便于调试和写测试。不要用std::rand()：它的实现质量与平台相关，且全局状态容易被别处调用打乱。
三、求解：广度优先搜索
边权都是 1（走一格算一步）时，BFS 首次到达终点时的路径就是最短路径。用一个prev数组记录每个格子是从哪个格子走来的，到达终点后沿prev回溯即可。下面的solve是Maze的成员函数，为节省篇幅单独列出，实际写在类定义内部。
// 适用于 C++17
#include <queue>
#include <utility>
std::vector<std::pair<int, 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::vector<int> prev(static_cast<std::size_t>(total), -1);
std::queue<int> 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_cast<std::size_t>(nid)] != -1) continue; // 已访问
prev[static_cast<std::size_t>(nid)] = id;
q.push(nid);
}
}
std::vector<std::pair<int, int>> path;
int goal = total - 1;
if (prev[static_cast<std::size_t>(goal)] == -1) return path; // 不可达
for (int cur = goal; cur != 0; cur = prev[static_cast<std::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负责驱动。
// 适用于 C++17
#include <iostream>
void 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 回不到 A
at(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::vector<int> 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 时用 BFS
std::queue<int> 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) | 与格子数线性相关 |
迷宫的关键在于把"生成"和"求解"当成两件事：生成负责构造一棵树，求解负责在这棵树上找路。只要表示法统一（墙在格子上、方向顺序固定、反方向用异或求得），两个算法可以各自替换而互不影响。
