G家 generating maze这道高频DFS就够吗

有没有高人帮忙解答一下，刷题初期，random generating maze
看到wiki上DFS是最基本解法，https://en.wikipedia.org/wiki/Maze_generation_algorithm 后面还有各种高段位的，比如Randomized Prim's algorithm等等几种，
但是感觉都只是本题能用上，不太具有普适意义，有必要看和会写吗，还是会dfs就行，有几种每种都要还挺难~

真正onsite面试的时候就会发现，能在45分钟内把这个DFS写出来并跑几个test case就不错了LOL

格罗鸽鸽飞 发表于 2019-11-7 23:34
真正onsite面试的时候就会发现，能在45分钟内把这个DFS写出来并跑几个test case就不错了LOL

居然是这样，我看地里有的人问本题答案，然后加米最多的给的wiki的链接，还有知乎的链接，各种复杂。
感谢解惑省好多时间~

刷题就困星人 发表于 2019-11-8 13:47
居然是这样，我看地里有的人问本题答案，然后加米最多的给的wiki的链接，还有知乎的链接，各种复杂。
感 ...

建议最好经常找人讲讲题或者模拟个面试啥的，真到了onsite面试的时候，题目不是像LeetCode那样清晰，面试官往往只给你一个题意，一些具体的输入限定需要你自己去跟面试官讨论，然后写代码的时候也要一直跟他交流，所以跟自己在电脑上敲代码的感觉是完全不一样的， 如果平时没有练习或者算法基础不够的话，可能限定时间内会写不完。Anyway，加油。

格罗鸽鸽飞 发表于 2019-11-8 14:00
建议最好经常找人讲讲题或者模拟个面试啥的，真到了onsite面试的时候，题目不是像LeetCode那样清晰，面试 ...

你说的是G家特定的吗，大佬？还是每家都是。加油也好难啊，朋友有帮我解答一些难题，不过架不住前刷后忘还是段位不够~

刷题就困星人 发表于 2019-11-14 05:45
你说的是G家特定的吗，大佬？还是每家都是。加油也好难啊，朋友有帮我解答一些难题，不过架不住前刷后忘 ...

额其实都是一样的啦，真正面试的时候不是说你闷头把题做出来就完事了，地里也有很多教面试的帖子，我就不献丑了，你可以搜着看一下，祝好运。

格罗鸽鸽飞 发表于 2019-11-14 12:50
额其实都是一样的啦，真正面试的时候不是说你闷头把题做出来就完事了，地里也有很多教面试的帖子，我就不 ...

你可以帮我答下另外一道题吗大哥，https://www.1point3acres.com/bbs/thread-570291-1-1.html
没人理我~是不是哪里发错喃？~会不会都先谢谢谢你喃~

找到一个不错的方案：Union Find
https://courses.cs.washington.ed ... oint-union-find.pdf

麻倉枼 发表于 2020-1-7 02:11
找到一个不错的方案：Union Find
https://courses.cs.washington.edu/courses/cse326/08sp/lectures/18-di ...

我来说下我的体会吧，正好昨天自己写了个程序。
大多数迷宫都把4面墙当作路的属性，G家迷宫路和墙是分开的。因为要每次走两个格子，所以还是DFS比较方便。

我是先写了普通DFS，然后通过简单的修改实现prim算法。加个List把所有能继续走的点都存起来，然后random就行了。

普通DFS和Prim的区别就是，普通DFS会有一条主线，分叉都很短，基本上没有分叉＋分叉的可能，就是一条路走到头。
Prim的话就比较像是个迷宫了，分叉＋分叉