68、实战：迷宫生成与求解（DFS/BFS+回溯）

迷宫问题，说实话是算法入门的一道经典门槛。我记得自己刚学C++那会儿，第一次用DFS跑通一个10x10的迷宫，兴奋得差点把屏幕拍碎。后来在项目中做路径规划，发现底层逻辑跟迷宫求解几乎一模一样——只不过换成了网格地图和机器人坐标。

今天咱们就把迷宫生成和求解一起拿下。你想想看，能自己生成迷宫，再亲手把它解开，这种掌控感还是很爽的。

迷宫的数据结构设计

迷宫本质上是个二维网格。每个格子要么是墙，要么是路。我个人习惯用二维数组来表示：

const int ROWS = 10;
const int COLS = 10;
int maze[ROWS][COLS] = {0}; // 0表示路，1表示墙

但这里有个坑——如果你直接用0/1表示，生成迷宫时很难处理「墙的厚度」问题。我建议用结构体：

struct Cell {
    bool visited;   // 是否访问过
    bool walls[4];  // 上右下左四面墙
    // 0:上, 1:右, 2:下, 3:左
};

每个格子维护自己的四面墙。这样生成迷宫时，只需要「拆墙」就行了。

迷宫生成：递归回溯法

生成迷宫的方法很多，我个人最常用的是递归回溯（Recursive Backtracking）。说白了就是DFS的思路：

1. 从起点出发，随机选一个未访问的邻居
2. 拆掉中间的墙，走过去
3. 递归继续
4. 如果走不动了，回溯到上一个格子

代码实现大概长这样：

void generateMaze(int r, int c) {
    maze[r][c].visited = true;
    
    // 随机打乱方向
    vector<int> dirs = {0,1,2,3};
    random_shuffle(dirs.begin(), dirs.end());
    
    for (int d : dirs) {
        int nr = r + dir[d][0];
        int nc = c + dir[d][1];
        
        if (nr >= 0 && nr < ROWS && 
            nc >= 0 && nc < COLS && 
            !maze[nr][nc].visited) {
            
            // 拆墙
            maze[r][c].walls[d] = false;
            maze[nr][nc].walls[(d+2)%4] = false;
            
            generateMaze(nr, nc);
        }
    }
}

嗯，这里要注意——random_shuffle 在C++17之后被标记为弃用了，建议用 shuffle 配合随机数引擎。我在项目里吃过这个亏，编译警告没当回事，后来升级编译器直接报错。

迷宫求解：DFS与BFS

迷宫生成好了，接下来就是求解。两种主流方法：DFS和BFS。我分别说说它们的适用场景。

DFS（深度优先搜索）

DFS的思路很简单：一条路走到黑，走不通就回头。用栈或者递归实现：

bool solveDFS(int r, int c, int er, int ec) {
    if (r == er && c == ec) return true;
    
    visited[r][c] = true;
    
    for (int d = 0; d < 4; d++) {
        if (maze[r][c].walls[d]) continue; // 有墙，走不了
        
        int nr = r + dir[d][0];
        int nc = c + dir[d][1];
        
        if (!visited[nr][nc] && solveDFS(nr, nc, er, ec)) {
            path.push_back({nr, nc}); // 记录路径
            return true;
        }
    }
    return false;
}

DFS找到的路径不一定是最短的，但代码简单。如果你只需要「有没有路」，DFS就够了。

BFS（广度优先搜索）

BFS保证找到最短路径。用队列实现，一层一层往外扩：

bool solveBFS(int sr, int sc, int er, int ec) {
    queue<pair<int,int>> q;
    q.push({sr, sc});
    visited[sr][sc] = true;
    
    // 记录前驱节点，用于回溯路径
    pair<int,int> prev[ROWS][COLS];
    
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        
        if (r == er && c == ec) {
            // 回溯路径
            reconstructPath(prev, sr, sc, er, ec);
            return true;
        }
        
        for (int d = 0; d < 4; d++) {
            if (maze[r][c].walls[d]) continue;
            
            int nr = r + dir[d][0];
            int nc = c + dir[d][1];
            
            if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                prev[nr][nc] = {r, c};
                q.push({nr, nc});
            }
        }
    }
    return false;
}

完整流程与SVG图解

我把整个流程画了张图，方便你理解各个模块之间的关系：

可视化与调试技巧

光有算法还不够，你得能「看到」迷宫长什么样。我习惯用控制台输出：

void printMaze() {
    for (int r = 0; r < ROWS; r++) {
        // 打印上边界
        for (int c = 0; c < COLS; c++) {
            cout << "+";
            cout << (maze[r][c].walls[0] ? "---" : "   ");
        }
        cout << "+" << endl;
        
        // 打印左右边界
        for (int c = 0; c < COLS; c++) {
            cout << (maze[r][c].walls[3] ? "|" : " ");
            cout << "   ";
        }
        cout << "|" << endl;
    }
    
    // 打印底部边界
    for (int c = 0; c < COLS; c++) {
        cout << "+---";
    }
    cout << "+" << endl;
}

调试的时候，我还会把路径用特殊字符标出来。比如用 * 表示路径上的格子，一眼就能看出对不对。

性能对比

算法	时间复杂度	空间复杂度	路径质量	适用场景
DFS（递归回溯）	O(N)	O(N) 递归栈	不一定最短	迷宫生成、连通性判断
BFS	O(N)	O(N) 队列	最短路径	寻路、游戏AI
DFS（显式栈）	O(N)	O(N) 栈	不一定最短	避免递归深度过大

N 是格子总数，即 ROWS × COLS。对于100x100的迷宫，两种算法都能在毫秒级完成。但如果你用递归DFS，栈深度可能达到10000层——有些编译器默认栈空间不够，会崩。我建议超过50x50就用显式栈。

好了，迷宫生成与求解的核心内容就这些。代码写完之后，你可以试试不同尺寸的迷宫，看看DFS和BFS的路径差异。嗯，动手跑一遍比看十遍都管用。