AI, 迷宫生成

Google NYC 挺喜欢问这个的，估计是因为 NYC office 的人都搞 map..

普林斯顿的 Robert Sedgewick 大爷在他的算法课里面讲过几种：最简单的一种，随机方向 DFS "挖墙". 另外两个稍微 fancy 的一点，本质上就是把迷宫当做一个 graph，去做一个 minimum spanning tree.

https://en.wikipedia.org/wiki/Maze_generation_algorithm

面试 google 这个程度的，写个随机 DFS 生成就可以了~

https://www.youtube.com/watch?v=8Ju_uxJ9v44

直接看７：３０秒的移墙函数

a.i-b.i ==1 ; a.i-b.i==-1; a.j-b.j==1; a.j-b.j==-1;判断cell a 和cell b相对位置关系移除墙

Make the initial cell the current cell and mark it as visited

1. While there are unvisited cells
   1. If the current cell has any neighbours which have not been visited
      1. Choose randomly one of the unvisited neighbours
      2. Push the current cell to the stack
      3. Remove the wall between the current cell and the chosen cell
      4. Make the chosen cell the current cell and mark it as visited
   2. Else if stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell