迷宫生成

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies

一道高频题，如何在一个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;
}

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

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

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

步惊云 发表于 2019-3-7 13:47
我在youtube上看了几个总结, 大致有三种方法.

只记得两个了.

顶楼没有放PRIM是因为虽然PRIM的效果更自然，但是感觉面试时如果没有特殊要求，我感觉只记一个递归的就可以。followup难在特别的requirement上。这几种哪一种更灵活呢？

1. Start with a grid full of walls.
   
2. Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
   
3. While there are walls in the list:
   
4.   Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:
   
5.     Make the wall a passage and mark the unvisited cell as part of the maze.
   
6.     Add the neighboring walls of the cell to the wall list.
   
7.   Remove the wall from the list.

复制代码

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

假这长宽都是长度至少为3的奇数, 因为这样才好保证墙壁的厚度为1, 先把所有的数组设为墙壁，从最左上角开始，每次可以随机往四个方向走两步把墙打通，假如所有可以打的墙都打通了，数组会变成这样

    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００

    零是路，一是牆
   
为求确保只有一条路线，必须避免

    000
    010
    000

的情况. 也就是說，離當前座標距離為二位置如果已經是零了，就不能打通開路線, 最终所有x, y 皆为偶数的座标全部都会被打通，都是奇数的座标必定为墙, 一奇一偶的可能被打通可能不被打通, 但一定不会出现一个环的路径

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies

以下为代码打印出范例，不知思路是否完全正确，请大神指教

[0, 0, 0, 0, 0]
[1, 1, 1, 1, 0]
[0, 0, 0, 1, 0]
[0, 1, 0, 1, 0]
[0, 1, 0, 0, 0]

[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[0, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 0]
[0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0]

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

没有明白的地方是：

離當前座標距離為二位置如果已經是零了就不能打通開路線

仅仅这个条件是否能保证没有环。环的种类如果是不规则的你这个算法一定可以防止吗？

1. 0011111000011
   
2. 1011110011001
   
3. 1000000111100
   
4. 1111110111110
   
5. 1111110111100
   
6. 1111110011101
   
7. 1111111000001
   
8. 1111111111100
   

复制代码

14417335 发表于 2019/03/09 08:14:06

仅仅这个条件是否能保证没有环。环的种类如果是不规则的你这个算法一定可以防止吗？
[mw_shl_code=bash,false]0011111000011
1011110011001
100...

我的想法是：如果把他想成一个最多三个儿子的N叉树，那一个树的任两个截点是能保证不会有环的，也就满足了只有单一路线。这个深度优先搜索的作法，就像是从是把左上角当为根节点来创建一个树，以经设为0的格子表示已经被创建了的节点。已经visited 的node不再去打通，一个节点就只会有一个parent ，有点像union Find 如果已经在同一个集合了就不必再做merge 的动作


其实我也不是很确定自己是不是对的（小弟我证明比较弱），所以希望小伙伴们也能讨论和指证

kaipeng21 发表于 2019-3-9 10:22
我的想法是：如果把他想成一个最多三个儿子的N叉树，那一个树的任两个截点是能保证不会有环的，也就满 ...

两点观察：
1. dest没用到。其实可能也无所谓因为题目并未要求。
2. 从生成的matrix来看没发现有三个儿子的分支。最多两个儿子。可能是概率所致？

14417335 发表于 2019-3-9 11:12
两点观察：
1. dest没用到。其实可能也无所谓因为题目并未要求。
2. 从生成的matrix来看没发现有三个儿 ...

关于第一点
我没用到起点和终点，但如果起点和终点座标都是(2x, 2y)，皆为偶数，那是保证一定会被打通的点，所有的奇数座标(2x+1,2y+1)则必为墙，座标一奇一偶的状况可能被打通可能不被打通，如果题目有要求起始点和终点位置，那可能还要再做一些处理吧

关于第二点
我有点证明不太出来 “是否一定不会产生三个儿子” 的状况，但应该不是概率问题，而是DFS造成的特性造成．因为DFS的关系一定是由最深的节点开始去找Neighbor打通，直到没方向走了才会回朔到Parent再尝试往其他方向打通，而大部分的状态下（也可能是全部，我暂时想不到反例），深度较深的子节点都会把Parent可能往其他方向去节点都先Visited掉了．
比如
0111111 A. 随机往下 （还能往右）
0111111
0111111
---------------
0111111 B. 随机往右（也只能往右）
0111111
0001111
---------------
0111111 C. 随机往右 （还能往上）
0111111
0000011
---------------
0111011 D. 随机往上 （还能往右）
0111011
0000011
---------------
0100011 E. 随机往左 （还能往右）
0111011 （这也把parent A, C的可能性杀掉了）
0000011
---------------
0100011 Ｆ. 没有方向走，回朔到E
0111011
0000011
---------------
0100000 E. 随机往右 （也只能往右）
0111011
0000011
---------------
0100000 G. 随机往下 （也只能往下）
0111010 （同时也把parent D的可能性杀掉了）
0000010

剩下的回朔到起点，回朔间没有任何节点能再能往四周打通
感觉好像Parent 的其他分支大概率（我也不敢说一定，也不确定怎么证明）是会被Child先 Visited 的

kaipeng21 发表于 2019-3-9 12:48
关于第一点
我没用到起点和终点，但如果起点和终点座标都是(2x, 2y)，皆为偶数，那是保证一定会被打通的 ...

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

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

果然找到一处：

1. <!DOCTYPE html><html><head><style>div.maze {line-height: 90%;transform: scale(2, 1) translate(25%, 0%);}</style></head>
   
2. <h2>Maze</h2><div class="maze">
   
3. <pre>
   
4. ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
   
5. ▓   ▓         ▓ ▓
   
6. ▓▓▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓
   
7. ▓ ▓ ▓ ▓     ▓   ▓
   
8. ▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓ ▓
   
9. ▓ ▓   ▓ ▓   ▓   ▓
   
10. ▓ ▓▓▓▓▓ ▓ ▓▓▓ ▓▓▓
    
11. ▓       ▓       ▓
    
12. ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
    
13. </pre></div></body></html>

复制代码

注意蓝色的小点，那个地方出现了三个儿子。