UVa 705

Maze Exploration

from Volume 2. Data Structures :: Graphs

Description

输入一张迷宫图，全部由 '/'、'' 组成。这样，迷宫就变成一个斜线迷宫。因为输入全为 '/' 、'' ，因此，这个迷宫将由全部宽度为1的路径组成。 要求输出迷宫中有几个回环，即封闭的路径有几条，其中最长的有多长。

Solution

经典的斜线迷宫题。可用 FloodFill 解决。

首先知道，没有封闭的路径，必然将通往图的外面。所以只要从图的边界开始 FloodFill，把不满足条件的排除后。再对每一个点去 FloodFill 即可求出所要的解。

而对于斜线的处理，有三种方法：

1. 九分法：将所有的格子都扩大成 9 * 9 的格子，然后只要用普通的 FloodFill 对每格上下左右四个方向的 DFS 就可以。
2. 四分法：将所有的格子扩大成 4 * 4 的格子，然后依然是对每个格子向八个方向 FloodFill ，但是要注意，在 2 * 2 格子中的某点向周围Flood 的时候，只能到达上下左右的 2 * 2格子。反之如果 FloodFill 后依然在原先的 2 * 2格子，或者对角线方向的 2 * 2 格子的，将会是穿过了 '/' 的非法情况，需要排除掉。
3. 光线反射法：模拟一条光线在迷宫中照射，对于每个格子，光线可能从四个方向射进来。在 FloodFill 的时候，判断光线来的方向，找到下一个 FloodFill 的格子即可。

三种方法，第一种较为简单，但是要将原图长宽各扩大三倍，得到一张原图九倍大的新图。而第二种方法，只要将原图扩大四倍，但是要判断要FloodFill的格子是否可以FloodFill。而第三种方法，较为复杂，对光线进来的四个方向都要判断反射出去的方向，可以用一个 enum 配合 const 数组来映射，好处就是不用扩大原图，时间复杂度相对前两种，常数较低。