3.2.2　迷宫的求解

问题：这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。

求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。

需要解决的四个问题如下。

1.表示迷宫的数据结构

设迷宫为m行n列，利用maze［m］［n］来表示一个迷宫，maze［i］［j］＝0或1，其中0表示通路，1表示不通。当从某点向下试探时，中间点有8个方向可以试探（见图3－5），而4个角点有3个方向，其他边缘点有5个方向。为使问题简单化，我们用maze［m＋2］［n＋2］来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为8，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。

图3－5表示的迷宫是一个6×8的迷宫。入口坐标为（1，1），出口坐标为（6，8）。

图3－5 用maze［m＋2］［n＋2］表示的迷宫

迷宫的定义如下：

2.试探方向

在上述表示迷宫的情况下，每个点有8个方向去试探，如当前点的坐标（x，y），与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，如图3－6所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move［8］中，在move数组中，每个元素由两个域组成，x为横坐标增量，y为纵坐标增量。move数组如图3－7所示。

move数组定义如下：

这样对move的设计会很方便地求出从某点（x，y）按某一方向v（0≤v≤7）到达的新点（i，j）的坐标：

i＝x＋move［v］.x； j＝y＋move［v］.y；

图3－6 与点（x，y）相邻的8个点及坐标

图3－7 增量数组move

3.栈的设计

当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。对于图3－5所示迷宫，依次入栈如图3－8所示。

图3－8 入栈顺序图

栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3－5所示迷宫，走的路线为：（1，1）1→（2，2）1→（3，3）0→（3，4）0→（3，5）0→（3，6）0（下脚标表示方向），当从点（3，6）沿方向0到达点（3，7）之后，无路可走，则应回溯，即退回到点（3，6），对应的操作是出栈，沿下一个方向即方向1继续试探，方向1、2试探失败，在方向3上试探成功，因此将（3，6，3）压入栈中，即到达了（4，5）点。

栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：

栈的定义仍然为：SeqStack s；。

4.防止重复到达某点

如何防止重复到达某点，以避免发生死循环。一种方法是另外设置一个标志数组mark［m］［n］，它的所有元素都初始化为0，一旦到达了某一点（i，j）之后，使mark［i］［j］置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点（i，j）后使maze［i］［j］置－1，以便区别未到达过的点，同样也能起到防止走重复点的目的。本书采用后者方法，算法结束前可恢复原迷宫。

迷宫求解算法思想如下：

（1）栈初始化；

（2）将入口点坐标及到达该点的方向（设为－1）入栈；

（3）while（栈不空）

算法3.5 迷宫求解

栈中保存的就是一条迷宫的通路。