作业帮PASCAL 老鼠走迷宫问题
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 17:31:20
PASCAL 老鼠走迷宫问题
PASCAL 老鼠走迷宫问题
PASCAL 老鼠走迷宫问题
一．实验内容：
耗子走迷宫问题.
用一个m行n列的二维数组来表示迷宫.数组中每个元素的取值为0或1.其中值0表示通路,值1表示阻塞,迷宫的入口在左上放（1,1）处,出口在右下方（m,n）处.要求求出从迷宫入口到出口有无通路,若有通路则指出其中一条通路的路径,即输出找到通路的迷宫数组,其中通路上的“0”用另外一个数字8替换,同时打印出所走通路径上每一步的位置坐标及下一步的方向.
二．算法说明：
（1）以二维数组maze[m][n]表示迷宫,并设maze[1][1]处为迷宫入口,maze[m[n]处为迷宫出口,迷宫中的任一位置以maze[i][j]来表示.
（2）对于迷宫中的每个位置（i,j）处,可能移动的路线可以有八个方向,用一个二维数组move表示这八个方向上坐标的增量,并把这八个方向从正东起按顺时针方向编上序号,则move[k][0]表示第k个方向上i的增量,move[k][1]表示第k个方向上j的增量.
move数组的方向增量表内容如下：
k
1
2
3
4
5
6
7
8
move[k][0]
0
1
1
1
0
-1
-1
-1
move[k][1]
1
1
0
-1
-1
-1
0
1
（3）当处于迷宫边缘时,它的下一个位置不再有八种可能,甚至只有三种可能.所以,为了简化边界位置的检测,将二维数组maze[m][n]扩充到maze[m+2][n+2],且令其四周边界位置的值均为1.
（4）计算机解迷宫,要用一步一试探的方法.为此在开始每一步时,都要从正东方向起,沿顺时针方向检测.当探测到某个方向上下一个位置的值为0时,就沿着此方向走一步,当这一步周围剩下的七个方向的上的值均为1时,则退回一步重新检测下一方向.在这过程中,建立一个mark[m+2][n+2]数组来记录某位置是否走过,走过用1记,未走过用0记.据此,可以用递归的思路来解决该问题.
（5）具体的算法可以概括如下：
走迷宫过程中,如果当前位置（i,j）（初始以入口为当前位置）已到达出口,即（i,j）=（m,n）,则说明已找到一条通路,返回值1,表示走通,结束递归过程；如果当前位置的各个方向上都没有找到通向出口的路径,则递归返回值0,表示未走通,若此时的位置在入口处,给出“没有通路”的信息,结束递归；如果对当前位置的各个方向依次试探的过程中,发现某个方向的试探位置可以走（即maze与mark数组中该位置的值均为0）,则把试探位置作为调用参数递归调用走迷宫过程,同时对调用的返回值进行判断,若调用返回值为1,则表示当前位置在走通的路径上,因此要记录下该位置,且递归返回1.在记录走通的每步位置时,考虑到递归的特点,若要正序打出走通的路径,我们则可以另入口和出口颠倒,即可实现目的.