迷宫求解问题.doc

迷宫求解问题

摘要:用矩阵表示迷宫,将矩阵表示的迷宫转换成无向图,用邻接表存储。对无向图从入口结点开始广度优先搜索,用一个一维数组存储各个结点的前驱结点的编号,通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2,依次类推直到找到出口结点。
关键字:矩阵迷宫求解

一、需求分析

:
迷宫求解问题。迷宫是一个如下所示的m行n列的0-1矩阵,0表示无障碍,1表示有障碍。设入口为(1,1),出口为(m,n),每次移动只能从一个无障碍的单元移到周围8个方向的任意一个无障碍的单元,编写程序给出一条通过迷宫的路径或者报告一个“无法通过”的信息。
入口->(0,0,0,1,0,0,0,1,0,0,0,1,0,0,1)
(0,1,0,0,0,1,0,1,0,0,0,1,1,1,1)
(0,1,1,1,1,1,0,1,0,0,1,1,1,0,1)
(1,1,0,0,0,1,1,0,1,1,0,0,1,0,1)
(1,0,0,1,0,1,1,1,1,0,1,0,1,0,1)
(1,0,1,0,0,1,0,1,0,1,0,1,0,1,0)
(1,0,1,1,1,1,1,0,0,1,1,1,1,0,0)
(1,1,1,0,1,1,1,1,0,1,0,1,0,1,0)
(1,0,1,0,1,0,1,1,1,0,1,0,0,0,1)
(0,1,0,1,0,1,0,0,0,1,1,0,0,1,0)->出口
:
迷宫问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的,每个位置上都没有障碍,且每个位置(第一个除外)都是前一个位置的东、南、西或北的邻居,如图C。
计算机走迷宫的方法是,采取一步一步试探的方法。每一步都从东开始,按顺时针对8个方向进行试探,若某方向上maze(x,y)=0,表示可以通行,则走一步;若maze(x,y)=1,表示不可以通行,须换方向再试,直到8个方向都试过;若maze(x,y)均为1,说明此步已无路可走,需退回一步,在上一步的下一个方向重新开始探测。为此,需设置一个栈,用于记录所走过的位置和方向(i,j,dir)。当退回一步时,从栈中退出一个元素,以便在上一个位置的下一个方向上探测,如又找到一个行进方向,则把当前位置和方向重新进栈,并走到新的位置。
若探测到位置(m,n),则已经到达迷宫的出口,可以停止探测,输出存在栈中的路径;如果在某一位置的8个方向上堵塞,则退回一步,继续探测;如果已退到迷宫的入口(栈中无元素),则表示此迷宫无路径可走。

二、概要设计

主要思想:
1. 用矩阵表示的迷宫;
2. 将矩阵表示的迷宫转换成无向图,用邻接表存储;
3. 对无向图从入口结点开始广度优先搜索;
4. 用一个一维数组存储各个结点的前驱结点的编号;
5. 通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2;
6. 依次类推直到找到出口结点。

基本设计算法:
1. 设置数组maze[MAX][MAX]来模拟迷宫,
2. maze [i][j]=0表示该方格所在的位置可通行, A[i][j]=1则表明该位置不能通行;
3. 定义无向图G,迷宫的规格(行、列)、,其结点数同迷宫(数组maze [MAX][MAX])的方格个数。
4. 每一个结点的邻接结点为其相邻(从点在数组maze [][]中所处的位置的角度)的八个点中值为0的点,按结点的顺序依次找出每一个点的邻接点,此即完成迷宫图的数组表示转化为无向图表示,G用邻接表存储;
5. 采用图的广度优先遍历的方法,从入口结点开始遍历,直到碰到出口结点为止。并设置record数组来记录结点i在广度优先遍历过程中的前驱结点的编号record[i];
6. 这样(record[i],i)表示存在从结点record[i]到i的边,这样就可以从出口顶点在图中的编号回溯出口顶点,如此,一条从入口到出口的最短路径就找到了。在定义record数组是将所有初始值设为-1,只是为了判断是否存在从入口到出口的路径, 因为如果出口结点i的record[i]值为-1则表明遍历过程没有找到出口,也就是说此迷宫无解.
7. 反之record[i]!= -1,则此迷宫一定是有解的,因为只有遍历过程中找到了出口I,才会改变record[i]的值,而这个改变后的值是不可能为-1的;
8. 输出从入口到出口的路径,用回溯法,只需将图中结点的编号换算成数组maze的坐标即可。

三、详细设计

1. 基本过程的算法:设定a[0][0]为入口位置;
do{
若当前位置可通,
则{将当前位置插入栈顶;
若该位置是出口