答案：使用DFS结合随机性生成迷宫，从起点开始标记访问，随机打乱方向顺序，打通相邻未访问格子间的墙并递归探索，最终形成连通无环的迷宫结构。
用深度优先搜索（DFS）结合随机性来生成迷宫，是一种常见且效果不错的算法。核心思路是模拟“回溯探索”的过程，从起点出发，随机选择未访问的方向前进，打通墙壁，直到所有格子都被访问过，形成一个连通无环的迷宫。
算法基本原理
将迷宫看作一个二维网格，每个格子是一个“房间”。通过打破格子之间的墙来连接它们。使用深度优先搜索，但每次选择下一个方向时采用随机顺序，这样可以生成结构多变的迷宫。
关键点：
- 从任意起点开始（通常选左上角）
- 标记当前格子为已访问
- 随机打乱上下左右四个方向的探索顺序
- 对每个方向，若相邻格子未访问，则打通中间的墙，递归进入该格子
- 使用栈或递归实现回溯
代码实现（递归版本）
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int WIDTH = 21; // 宽度必须为奇数，方便表示墙和格子
const int HEIGHT = 21; // 高度也必须为奇数
vector<vector<bool>> visited(HEIGHT, vector<bool>(WIDTH, false));
vector<vector<bool>> maze(HEIGHT, vector<bool>(WIDTH, true)); // true 表示墙
// 四个方向：上、右、下、左
int dx[4] = {0, 2, 0, -2};
int dy[4] = {-2, 0, 2, 0};
void generate(int x, int y) {
visited[y][x] = true;
maze[y][x] = false; // 当前格子设为通路
// 定义方向索引并随机打乱
vector<int> dirs = {0, 1, 2, 3};
random_shuffle(dirs.begin(), dirs.end());
for (int i : dirs) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx > 0 && nx < WIDTH-1 && ny > 0 && ny < HEIGHT-1 && !visited[ny][nx]) {
maze[ny + dy[i]/2][nx + dx[i]/2] = false; // 打通中间墙
generate(nx, ny);
}
}
}
void printMaze() {
for (int i = 0; i < HEIGHT; ++i) {
for (int j = 0; j < WIDTH; ++j) {
cout << (maze[i][j] ? "#" : " ");
}
cout << endl;
}
}
int main() {
srand(time(0));
// 起点设在 (1,1)
generate(1, 1);
// 可选：设置入口和出口
maze[0][1] = false;
maze[HEIGHT-1][WIDTH-2] = false;
printMaze();
return 0;
}
关键细节说明
网格尺寸为何是奇数？ 因为每个格子之间有墙，若用 21x21 的网格，实际表示 10x10 个房间，墙和通路交错分布。坐标 (1,1)、(1,3) 等为房间位置，偶数坐标多为墙。
立即学习“C++免费学习笔记（深入）”；
如何打通墙？ 从 (x,y) 走到 (x+2,y)，中间墙在 (x+1,y)，所以将该位置设为 false。
random_shuffle 提升随机性 每次随机打乱方向顺序，避免固定模式，让迷宫更自然。
递归深度问题 大迷宫可能导致栈溢出。可改用显式栈迭代实现，逻辑一致但更安全。
基本上就这些。算法简单，生成的迷宫连通性好，适合游戏或演示使用。
