迷宫生成

14417335 发表于 2019/03/10 09:01:53


我觉得你这个算法还是挺不错的。赞！

但是你的解释我不能认同。DFS的道理我一开始就知道。所以我才说是概率。但是为了看起来方便，分享一下我的办法：生成了html。这样用浏览器看起来比较直观。
...

感谢144大神指教

对于m * n的maze:
1/ 生成m * n个cell
2/ 对每个cell建立与其neighbors的connection
3/ run kruskal, count = m * n - 1，每次列举一个cell，检查其任何neighbor是否在同一个set中(union find), 如果不在则knockdown wall，count--
4/ 这样生成的maze任意两点之间必有通路且唯一

https://algs4.cs.princeton.edu/41graph/Maze.java.html
我看这个好像可以，不过本**不确定。

kaipeng21 发表于 2019-3-9 04:36
假这长宽都是长度至少为3的奇数, 因为这样才好保证墙壁的厚度为1, 先把所有的数组设为墙壁，从最左上角开始 ...

感谢！好像终于有点看懂这道题了，想问下这个解法里是怎么保证从start开始到dest结束的啊 generate_maze里面好像没有dest相关，也不是从start开始的？

补充内容 (2019-3-26 14:26):
哦看到了 原来没管这个啊……

这是狗家的那个高频 题么？楼主在写标题的时候标明是哪个公司的高频 题么？谢谢！

如果把每个cell当成一个节点，联通的cell当成一条边，迷宫就是一个图。

任意两cell只有一条路径，说明cell组成的图必须是一个树，生成一个树用bfs或dfs都可以。具体方法就是随机找个cell做为root开始bfs，或dfs，打通那些有边链接的cell之间的wall。

此题的关键就是怎么保证生成的树是随机的。

随机化bfs:??? 每次要随机从bfs的queue里选一个元素弹出拓展邻居，把普通的fifo queue变成一个随机弹出元素的queue。注意优化时间复杂度，每次交换queue尾部元素和其中随机选取的一个元素的位置，再弹出此时的尾部元素，时间复杂度和正常bfs一致。

随机化dfs :? 每次按随机顺序访问四个方向上的邻居节点，也就是压入stack的顺序是随机的。时间复杂度也和正常dfs一致。

一道高频题，如何在一个2d矩阵中随机生成一个迷宫，墙的厚度只能为1

直接上C++代码：

// generate maze
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

int getDegree(int x, int y, vector<vector<char>> &maze) {
    int degree = 0;
    if (x > 0 && maze[x-1][y] == ' ') degree++;
    if (y > 0 && maze[x][y-1] == ' ') degree++;
    if (x < maze.size() - 1 && maze[x+1][y] == ' ') degree++;
    if (y < maze[0].size() - 1 && maze[x][y+1] == ' ') degree++;
    return degree;
}

void generateMaze(vector<vector<char>> &maze, int x, int y) {
    vector<vector<int>> dirs = {{0,1},{-1,0},{1,0},{0,-1}};
    random_shuffle(dirs.begin(), dirs.end());

    for (vector<int> dir : dirs) {
        int new_x = x + dir[0];
        int new_y = y + dir[1];

        if (new_x < 0 || new_y < 0 || new_x >= maze.size() || new_y >= maze[0].size() || maze[new_x][new_y] == ' ') continue;
        if (getDegree(new_x, new_y, maze) > 1) continue;
        maze[new_x][new_y] = ' ';
        generateMaze(maze, new_x, new_y);
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<vector<char>> test(10, vector<char>(10, '*'));
    generateMaze(test, 0, 0);
    for (auto a : test) {
        for (auto b : a) {
            cout<<b;
        }
        cout<<endl;
    }
    return 0;
}

我有个疑问，做dfs的时候不是有一个set用来检查目标点是否已经访问了吗。如果目标点已经被访问了那么就不考虑，这个方法不是已经可以避免图里有环出现。

所以加入这个条件的dfs生成的迷宫应该是没有环的，换言之就是只有一种路线可以从起点走到终点。我自己也写了程序，模拟了几次没见到有环。