迷宫问题的求解

《迷宫问题的求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序设计与算法综合训练》设计报告1学号：E11514064姓名：汪泓章年级：大一专业：计科项目名称：迷宫问题的求解完成日期：2016年6月28日1、需求分析(1)问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（2）基本要求：1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于教材第50页图3.4所示的迷宫，输出一条通路为：（1，1，1），（

2、1，2，2），（2，2，2），（3，2，3），（3，1，2），…。2）编写递归形式的算法，求得迷宫中所有可能的通路。3）以方阵形式输出迷宫及其通路。4）按照题意要求独立进行设计，设计结束后按要求写出设计报告。①输入输出的要求：②(i)求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。（ii）输出迷宫示意图③程序所能达到的功能：(i)实现一个以链表作存储结构的栈类型，以非递归算法求取所有通路和最短路径(ii)以一个递归算法，对任意输入的迷宫矩阵（1代表不通，0代表通路）求出所有通路2、概要设计i）设计中非递归程序的模块结构图图中

3、方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成main（）mapath（）mgpath（）：求解迷宫问题，即输出从（1，1）到（M，N）的全部路径和最短路径（包含最短路径长度）。当找到一条路径时，不使用return语句退出，而是出栈一次，重新回溯走另一条路径，并用minlen记录最短路径长度，Path数组记录最短路径。ii）程序的数据结构和数据库结构分析设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它

4、边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。图3增量数组moveiii、栈的设计当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为：top—>3,4,03,3,03,2,12,2,02,1,11,1,0栈中每一组数据是所到达的每点的坐

5、标及从该点沿哪个方向向下走的，对于图3迷宫，走的路线为：(1,1)0à(2,1)1à(2,2)0à(3,2)1à(3,3)0à(3,4)0（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedefstruct{intx,y,d;/*横纵坐标及方向*/}datatype;栈的定义为：SeqStacks;iv、达某点，以避免发生死循环：一种方法是另外设置一个标志数组mark[m][n]，它的所有元素都初始化为0，一旦到达了某一点(i,j)之后，使mark[i][j]置1，下次再试探这个位

6、置时就不能再走了。另一种方法是当到达某点（i,j）后使maze[i][j]置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的，此处采用后一方法，算法结束前可恢复原迷宫。1、详细设计伪码设计(1)栈初始化;(2)将入口点坐标及到达该点的方向（设为-1）入栈(3)while(栈不空){栈顶元素＝＞（x,y,d）出栈;求出下一个要试探的方向d++;while（还有剩余试探方向时）{if（d方向可走）则{（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if((x,ｙ)==(ｍ,n))结束;else重置d=0;}elsed++;}}算法如下：intpa

7、th(int&maze，intm,intn,intmove)//m,n为maze的一、二维长度，move为结构体数组存放了试探的4个方向坐标{SeqStacks;datetypetemp;intx,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Push_SeqStack(s，temp);阿while(!Empty_SeqStack(s)){Pop_SeqStack(s,＆temp);x=temp.x;y=temp.y;