PASCAL 老鼠走迷宫问题
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/27 00:55:16
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.在记录走通的每步位置时,考虑到递归的特点,若要正序打出走通的路径,我们则可以另入口和出口颠倒,即可实现目的.