迷宫问题的求解

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列，利用mazemn来表示一个迷宫，mazeij=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使

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

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

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

7、 (x ,)= =(,n) ) 结束 ; else 重置 d=0 ; else d+ ; 算法如下： int path(int &maze，int m, int n, int move) /m,n为 maze的一、二维长度，move为结构体数组存放了试探的4个方向坐标 SeqStack s ; datetype temp ; int x, 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)

8、 ;x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d<4) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ;Push_SeqStack ( s, temp ) ;x=i ; y=j ; mazexy= -1 ;if (x= =m&&y= =n) return 1 ; /*迷宫有路*/else d=0 ; else d+ ; /*while (d<4)*/ /*while (! Empty_SeqStack (s ) )*/ return 0 ;/*迷宫无路*/

9、栈中保存的就是一条迷宫的通路。4、 测试与分析迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0010001000100010000011010111001000010000010001010111100111000101110000005、 总结这次的项目，加强了我动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。6、 附录：源代码清单非递归#include &

10、lt;stdio.h>#include <string>#define M 9 /行数#define N 8/列数#define MaxSize 100/栈最多元素个数int mgM+2N+2 = /迷宫测试数据矩阵,左上角（1,1）为入口，右下角（9,8）为出口1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1

11、,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;struct int i;int j;int di; StackMaxSize,PathMaxSize;/定义栈和存放最短路径的数组int top=-1;/栈顶指针int count=1;/路径数计数int minlen=MaxSize;/最短路径长度void mgpath()/路径为:(1,1)->(M,N)int i,j,di,find,k;top+;/进栈Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;/初始结点

12、进栈while (top>-1)/栈不空时循环i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M && j=N)/找到了出口,输出路径 printf("%4d: ",count+);for (k=0;k<=top;k+) /以三元组输出路径printf("(%d,%d,%d) ",Stackk.i,Stackk.j,Stackk.di);if (k+1)%5=0) printf("nt");/输出时每5个结点换一行printf("n");if

13、 (top+1<minlen)/比较找最短路径for (k=0;k<=top;k+)Pathk=Stackk;minlen=top+1;mgStacktop.iStacktop.j=0;/让该位置变为其他路径可走结点top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di<4 && find=0)/找下一个可走结点di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;case 1:i=Stacktop.i;j=Stacktop.j+1;

14、break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/找到了下一个可走结点Stacktop.di=di;/修改原栈顶元素的di值top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/下一个可走结点进栈mgij=-1;/避免重复走到该结点else/没有路径可走,则退栈mgStacktop.iStacktop.j=0; /让该位置变为其他路径可走结点top-;printf(&q

15、uot;最短路径如下:n");printf("长度: %dn",minlen);printf("路径: ");for (k=0;k<minlen;k+)switch(Pathk.di)case 0:printf("(%d,%d,%s) ",Pathk.i,Pathk.j,"");break;case 1:printf("(%d,%d,%s) ",Pathk.i,Pathk.j,"");break;case 2:printf("(%d,%d,%s) &

16、quot;,Pathk.i,Pathk.j,"");break;case 3:printf("(%d,%d,%s) ",Pathk.i,Pathk.j,"");break;case-1: printf("(%d,%d,%s) ",Pathk.i,Pathk.j,"终点");break;if (k+1)%5=0) printf("nt"); /输出时每5个结点换一行printf("n");void main()printf("迷宫所有路径如下:n&

17、quot;);printf("三元组(i,j,di),(i,j)表示迷宫中的一个坐标,di:0;1;2;3;n");mgpath();递归#include<stdio.h>int flag=0; /flag用来标记是否路径全部走完int a1212=1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1

18、,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;int go(int x,int y) axy=2; if(x=9&&y=8) /迷宫出口设置为9,8 flag=1; if(flag!=1&&ax-1y=0) /判断向上是否有路 go(x-1,y); /这个go()纠结了好久，多了个return怎么都不行了 if(flag!=1&&axy+1=0) /判断向右是否有路 go(x,y+1); if(flag!=1&&ax+1y=0) /判断向下是否有路 go(x+1,y); if(flag!=1&&axy-1=0) /判断向左是否有路 go(x,y-1); if(flag!=1) axy=0; return flag; void main() int i,j,k,l,q; for(i=0;i<11;i+) /输出迷宫 for(j=0;j<12;j+) if(aij=0) printf(" "); if(aij=1)