C＋不知算法系列之迷宫问题中的“见山不是山”

1. 前言

迷宫问题是一类常见的问题。

初识此类问题，应该是“见山是山”，查询从起点到终点的可行之路。

有了广泛的知识体系之后，应该是"见山不是山"。会发现迷宫就是邻接矩阵，树和图中顶点的关系常用邻接矩阵描述，所以，迷宫问题可以转化为树、图的搜索问题。

最后便是“见山还是山”，能透过问题的表象，深化问题的本质，识破披着各色外衣的迷宫问题。

本文从不同的角度、全方位讲透迷宫问题中的“见山不是山”，让大家对迷宫问题有实质性的理解。

2. 迷宫问题

问题描述：

如下图迷宫地图中，表示障碍物，表示可通行。要求从起始点出发，检查是否有行之有效的通路，可以一直走到终点。迷宫问题的本质就是邻接矩阵的路径搜索问题。

常用的是和搜索算法。

2.1 设计数据结构

首先分析中的数据类型。

坐标类型：用来描述迷宫中每个单元格的位置。

方向类型：描述与每个单元格相邻的上、下、左、右 个单元格的关系。

迷宫类：描述本身以及迷宫相对应的操作函数。

2.2 检查连通性

使用检查迷宫的连通性。

洪水填充算法类似于古时候的"连坐法"，或说星星之火可以燎原也，从最初给定的位置开始，以蔓延之势，用填充与之相邻且值为 的单元格。本文中， 和都用于表示迷宫中的非障碍物区间。

洪水填充算法和后面的递归搜索算法相似，不同地方之处，会蔓延至所有满足条件的位置，搜索则是强调到通向目标的路径。

连通性结论：

测试：

输出结果： 迷宫中值为的位置全部被填充。

2.3 深度搜索

深度搜索可以使用非递归和递归 种方案实现。

2.3.1  非递归的思想

非递归深度搜索需要借助栈。

初始，把的坐标值压入栈中。

获取栈顶的坐标，检查此坐标的  个相邻的坐标是否可通行。如果可通行，则压入栈中，且标识此坐标已经访问过。如下图使用绿色表示已经访问过。

重复上述的的逻辑，如下图当是添加到单元格时栈中的内容。

与相邻的坐标分别是。其中已经访问过，则不需要再压入。栈中的坐标都是一路搜索下来可通行的位置。

继续获取栈顶坐标。随后找到与之相邻的，压入栈中；再得到栈顶的坐标，并找到与之相邻的。

Tips： 本文查找与栈顶坐标相邻的坐标是按的顺序。如果顺序不同，则会导致搜索过程不一样。

从栈顶得到，因此坐标位于。于是，从栈顶把此坐标删除。可得到一个结论，不是所有进入栈中的坐标都有机会成为有效路径中的一份子。本文称行之此处不能通行的坐标为坐标，也做相应的标记。也就是说，当坐标为坐标时，则从栈顶删除。

栈中的为坐标，删除。

从坐标开始，可以一路走到终点。把栈中的坐标全部输出便得到到的有效路径。

这里有一个问题要思考，栈中的值真的全是有效路径上的坐标？

其实不然，也许有些坐标进入栈中，只为备用。如到位置时，有 个可行方向。因这个方向可行，最终备用点没用上。所以，这些坐标也需要标记一下，本文称为。

对坐标进行不同颜色标记后，上图中的绿色坐标为最终有效路径。

2.3.2 编码实现

测试：

输出结果： 下图中的所示的坐标为有效路径描述。曾经进入过栈，但是死胡同坐标。 表示没有用上的备用坐标。

2.4 递归实现

可以使用，找出所有的路径。

测试代码：

注释如下代码：

会显示一条路径。如下图所示，表示递归过，但是的坐标。标记为大于等于 的位置为可正常通行。

如果打开如下代码。

显示所有路径，回溯不用判断死胡同坐标，回溯时会自动恢复原来的状态。

2.4 广度搜索

在家拖地时，如果从当前位置向前拖，然后再折回，这和深度优先搜索方式一样。另一种是从左向右方式，逐渐向远处外延，这和广度搜索一样。

广度优先类似于一石激起千层浪，一层层向外推动。

输出结果： 迷宫中的广度优先搜索相当于在无向图中查找路径，可以找到任何 个可通行位置的最短路径。这里只显示起点到终点的最短路径，如下所标记的坐标连接起来的路径。

3. 总结

迷宫本质是邻接矩阵，可用来存储树和图的关系。所以，迷宫问题可归结于树或图的路径搜索问题。