迷宫问题（1）—— 自动生成迷宫地图

在我学习数据结构期间，多次遇到使用特定的数据结构来实现走出迷宫的方案，因此兴趣使然，在网上找了一些自动生成迷宫地图的方法，发现基本还是使用的走迷宫时的算法，这里简单地设计一下，主要为了方便今后的代码实现和少写出一些bug。

迷宫模型的搭建和选择恰当的数据结构

因为生活中常见的迷宫都有以下特点：

1. 迷宫一般都是矩形的或者正方形的。
2. 迷宫一般只有墙作为障碍物，而且迷宫的周围就是一圈墙。
3. 迷宫中会有死胡同，需要往回走。
4. 迷宫应保证每一个点都是联通的，即不存在孤岛。
5. 尽量不要设计回路（可能对某些算法有较大影响）。
6. 迷宫的路径最好不要太明显，尽量保证有足够多的分支。

综合以上，我们选择使用二维数组来存储迷宫，并且把每一堵墙和每一个可以到达的位置模拟为数组中的行列坐标，这么做能够保证墙和路的地位是平等的，便于进行处理。至于如何区分两者，设置成数组中不同的值就好（比如map[1] [1] = 1 表示通路， map[2] [2] = -1 表示墙。

对于生成迷宫地图的初始地图，这里的设置十分巧妙。

假设有一片矩形区域，里面整齐排列着m行n列可以行走的位置，但是在这些位置之间，每两个位置都有一堵墙。

又假设自己是一个矿工，你需要通过打通一些墙来使得起点和终点之间相互连通，同时这些通路满足迷宫的基本特点，这样迷宫就生成了。

也可以比喻成在一张地图上有许许多多个散点，我们的目的是在不生成回路的前提下，将每两个相邻的散点连接起来，这有点像图的结构了。

迷宫随机生成算法——DFS

DFS不仅可以用来走迷宫，它同样可以用来生成迷宫，并且具有以下特点：

1. 可以打通所有的可到达位置。
2. 会有一条比较明显的主路。
3. 不会也不能生成回路（否则会陷入死循环或者打通所有墙）。

所以，基本思路是这样的：在当前位置寻找相邻的可以连通的位置（没有被打通过，在数组中需要跨越2个单位），在这些位置中随机选取一个（用rand( )函数），打通两个位置之间的墙，并且将当前位置用栈记录下来（或者其他顺序结构），再到达下个位置进行相同的操作。

如果没有可以连通的点了，就在栈中回溯之前的点，直到找到一个点有可以连通的相邻点，再重复上面的动作。

结束生成的条件是所有的点都没有可以连通的了，这是栈为空。