[分享]迷宫解决方案

JAY

A．迷宫生成：
我们假设迷宫是有许多个格子构成，如图。

图（1） 这样为一个格子。
下面是构成后的迷宫初始状态（这样的迷宫限制了宽高为大于3的奇数）。

图（2） 迷宫初始状态
具体步骤：
1．每一个白格子（路）之间的墙原本都是封闭的，我们从中随机找一个白格子，再随机搜索它的四周的白格子；
2．如果下一个白格子没走过，就走到下一个白格子，并打通它们之间的黑格子（墙），并且把上一个白格子压入栈；
3．如果一个白格子周围的格子都是走过的，那么就弹栈，继续判断上一白个格子，直到栈为空。

图（3） 用上述方法生成的一个迷宫，数字处为原来的黑格子（墙），编号是破墙的顺序，圆圈为破墙起始格。
此法类似于从一个随机的节点按深度优先生成一颗随机的3叉树。
由于上述方法生成的迷宫任何两点之间又且仅有一条通路，所以我们还可以自己打破若干面墙，形成有多条通路的迷宫，再定义它的起点、终点。

图（4） 生成后的效果，实心五星为起点，空心五星为终点。

B．走迷宫：
将迷宫看作一个图，每个空位点和周围相邻的空位点之间就是一条通路，因为所有的通路都是等价的，所以可以将其作为无权图考虑，因此只用广度优先遍历整个图即可找到两点之间的最短路径。
具体步骤：
1．我们从起点开始找最短路径，首先把起点压入队列；
2．弹出队列中的第一个格子，然后把与之连通的格子压入队列；
3．重复步骤2直到找到终点或者队列为空。

图（5） 寻路过程，数字表示该点被访问的顺序。

图（6） 寻路结果，线条表示访问过的路径，粗线条表示最短路径。