数据结构实验-迷宫问题

1、实验报告实验课名称：数据结构实验实验名称：迷宫问题班级：20130613学号：16姓名：施洋时间：2015-5-18一、问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒 子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行， 迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、 南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计 程序求解迷宫的一条通路。二、数据结构设计以一个mK

2、 n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素 0和1 分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为 1。根据题目中的数据，设置一个数组mg如下int mgM+2N+2=1,1,1,1,1,1,1,1,1,0,0,1,0。0,1,1,1,0。0,1,1,1,1,0,0,1,0。0,1,1,0,0。0。0,1,1,1,1,1,1,1,1,1；在算法中用到的栈采用顺序存储结构，将栈定义为Struct int i; / 当前方块的行号int j; / 当前方块的列号int di; /di是下一个相邻的可走的方位号stMaxSize;/ 定义栈int top=-1

3、 /初始化栈三、算法设计要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进 一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回 一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回 入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不 通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与 前进路径正好相反，因此可以借用一个栈来记录前进路径。方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的 坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即 顺时针方向）依次编号为0、1

4、、2、3.其增量数组move4如图3所示。-1001100-1move4 01 23x y图2数组move4(i-i, j)方位o方位3方位I o方位示意图如下:Q+LJ）方位2图3.方位图通路：通路上白每一个点有3个属性：一个横坐标属性i、一个列坐标属性 j和一个方向属性di ,表示其下一点的位置。如果约定尝试的顺序为上、右、下、 左（即顺时针方向），则每尝试一个方向不通时，di值增1,当d增至4时，表 示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一 条迷宫通路。(1)下面介绍求解迷宫(xi,yj )到终点(xe,ye )的路径的函数：先将入口进 栈(其初始位置设置为

5、一1),在栈不空时循环一一取栈顶方块(不退栈)若该 方块为出口，输出所有的方块即为路径，其代码和相应解释如下：int mgpath(int xi,int yi,int xe,int ye)/ 求 解 路 径为:(xi,yi)->(xe,ye)structint i;/当前方块的行号int j;/当前方块的列号int di;/di是下一可走方位的方位号 stMaxSize;/ 定义栈int top=-1;/初始化栈指针int i,j,k,di,find;top+;/初始方块进栈sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1;while (top>-

6、1)/栈不空时循环i=sttop.i;j=sttop.j;di=sttop.di; /取栈顶方块if (i=xe && j=ye)/找到了出口，输出路径printf("迷宫路径如下：n");for (k=0;k<=top;k+)printf("t(%d,%d)",stk.i,stk.j);if (k+1)%5=0)/每输出每5个方块后换一行printf("n");printf("n");return(1); /找到一条路径后返回1否则，找下一个可走的相邻方块若不存在这样的路径，说明当前的路径不

7、可能走通，也就是恢复当前方块为0后退栈。若存在这样的方块，则其方位保存在栈顶元素中，并将这个可走的相邻方块进栈(其初始位置设置为-1)求迷宫回溯过程如图4所示_回国挑线查找其他路往基4迷宫工-4:It程示堂图相邻可走方块，若没有这样则从当前方块回溯到前从前一个方块找到相邻可走方块之后， 再从当前方块找在、 的方快，说明当前方块不可能是从入口路径到出口路径的一个方块, 一个方块，继续从前一个方块找可走的方块。为了保证试探的可走的相邻方块不是已走路径上的方块，如（ i,j）已经进栈，在试探（i+1 , j）的下一方块时，又试探道（i, j）,这样会很悲剧的引起死循环，为此，在一个方 块进栈后，将对

8、应的 mg数组元素的值改为-1 （变为不可走的相邻方块），当退栈时（表示 该方块没有相邻的可走方块），将其值恢复0,其算法代码和相应的解释如下：find=0;while (di<4 && find=0)找下一个可走方块di+;switch(di)case 0:i=sttop.i-1;j=sttop.j;break;case 1:i=sttop.i;j=sttop.j+1;break;case 2:i=sttop.i+1;j=sttop.j;break;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一个可

9、走相邻方块if (find=1)找到了下一个可走方块sttop.di=di;修改原栈顶元素的 di值top+;下一个可走方块进栈sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;避免重复走到该方块else 没有路径可走，则退栈mgsttop.isttop.j=0;/ 让该位置变为其他路径可走方块 top-;将该方块退栈 return(0); 表示没有可走路径，返回0 (2)求解主程序 建立主函数调用上面的算法，将mg和st栈指针定义为全局变量void main() mgpath(1,1,M,N);四、界面设计设计很简单的界面，输出路径。五、运行测试与分析图5.基本

10、运行结果六、实验收获与思考思考：8个方向的问题1.设计思想(1)设置一个迷宫节点的数据结构。建立迷宫图形。(3)对迷宫进行处理找出一条从入口点到出口点的路径。输出该路径。（5）打印通路迷宫图。图6功能结构图当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序 号i, j来表示。而从i,j位置出发可能进行的方向见下图 7.如果i,j周围的位 置均为0值，则老鼠可以选择这8个位置中的任一个作为它的下一位置。将这 8 个方向分别记作：E （东）、SE （东南）、S （南）SW （西南）W （西）、NW （西 北）、N （北）和NE （东北）。但是并非每一个位置都有8个相邻位置。如果i,

11、j 位于边界上，即i=1 ,或i=m,或j=1,或j=n ,则相邻位置可能是3个或5个为 了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为mazem+2,n+2在迷宫行进时，可能有多个行进方向可选，我 们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规 定i,j的下一步位置的坐标是x,y,并将这8个方位伤的x和y坐标的增量预 先放在一个结构数组 move8中（见图8）。该数组的每个分量有两个域 dx和dy。 例如 要向东走，只要在j值上加上dy,就可以得到下一步位置的x,y值为i,j+dy。于是搜索方向的变化只要令方向值dir从0增至7

12、,便可以从move数组中得到从i,j点出发搜索到的每一个相邻点x,yx=i+movedir.dxy=j+movedir.dy但1P1J1.0+-1*g-Ip-1P-2 Jp-1*5:6-I*3图8向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为 0改为-1,这既 可以区别该位置是否已经走到过， 又可以与边界值1相区别。当整个搜索过程结 束后可以将所有的-1改回到0,从而恢复迷宫原样。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从（E）开始，按顺时针对8个方向进行探测，若某个方位上的mazex,y=0 ,表示可以 通行，则走一步；若mazex,y=1 ,表示此方向不可通

13、行须换方向再试。直至 8 个方向都试过，mazex,y均为1,说明此步已无路可走，需退回一步，在上一 步的下一个方向重新开始探测。为此需要设置一个栈，用来记录所走过的位置和 方向（i, j, dir）。当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上 探测，如又找到一个行进方向，则把当前位置和新的方向重新进栈， 并走到新的 位置。如果探测到x=m, y=n,则已经到达迷宫的出口，可以停止检测，输出存 在栈中的路径；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如 果已经退到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。2系统算法（伪代码描述）：(1)建立迷宫节点

14、的结构类型 stack口入迷宫图形0表示可以通1表示不可以通。用二维数组mazem+2n+2 进行存储。数组四周用1表示墙壁，其中入口点(1,1)与出口点(m, n)固定。(3)函数path()对迷宫进行处理，从入口开始：While(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1)For(扫描八个可以走的方向)If(找到一个可以走的方向)进入栈标志在当前点可以找到一个可以走的方向避免重复选择mazexy=-1不再对当前节点扫描If(八个方向已经被全部扫描过，无可以通的路)标志当前节点没有

15、往前的路后退一个节点搜索If(找到了目的地)输出路径退出循环未找到路径#define N2 11#define maxlen M2 / 栈长度#include <stdio.h>#include<iostream.h>#include <malloc.h>int M=M2-2,N=N2-2;/M*N迷宫的大小typedef struct /定义栈元素的类型int x,y,dir;elemtype;typedef struct / 定义顺序栈elemtype stack maxlen;int top;sqstktp;struct moved定义方向位移数组的元

16、素类型对于存储坐标增量的方向位移数组move int dx,dy;/void inimaze(int maze口N2)/ 初始化迷宫int i,j,num;for(i=0,j=0;i<=M+1;i+) 设置迷宫边界mazeij=1;for(i=0,j=0;j<=N+1;j+)mazeij=1;for(i=M+1,j=0;j<=N+1;j+)mazeij=1;cout<<"原始迷宫为："<<endl;for(i=1;i<=M;i+)for (j=1;j<=N;j+)num=(800*(i+j)+1500) % 327;/

17、根据 MN 的值产生迷宫if (num<150)&&(i!=M|j!=N) mazeij=1;elsemazeij=0;cout<<mazeij<<""，显示迷宫cout<<endl;cout<<endl;/inimazeIllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll void inimove(struct moved move)l

18、l 初始化方向位移数组 ll 依次为 East., Southeast, south, southwest, west, northwest, north, northeast move0.dx=0;move0.dy=1; move1.dx=1;move1.dy=1; move2.dx=1;move2.dy=0; move3.dx=1;move3.dy=-1; move4.dx=0;move4.dy=-1; move5.dx=-1;move5.dy-=1; move6.dx=-1;move6.dy=0; move7.dx=-1;move7.dy=1; ll void inistack(sqst

19、ktp *s)l* 初始化栈 *l s->top=-1; l*inistack*lint push(sqstktp*s,elemtype x) if(s->top=maxlen-1) return(false); else s->stack+s->top=x;l*栈不满，执行入栈操作*lreturn(true); l*push*l elemtype pop(sqstktp *s)l* 栈顶元素出栈 *l elemtype elem; if(s->top<0)如果栈空，返回空值 elem.x=NULL; elem.y=NULL; elem.dir=NULL;

20、return(elem); else s->top-; return(s->stacks->top+1);栈不空，返回栈顶元素 llpop llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll void path(int mazeN2,struct moved move,sqstktp *s)寻找迷宫中的条通路 ( int i,j,dir,x,y,f; elemtype elem; i=1;j=1;dir=0; maze11=-1; 设11为入口处 do ( x

21、=i+movedir.dx;/球下一步可行的到达点的坐标 y=j+movedir.dy; if(mazexy=0) ( elem.x=i;elem.y=j;elem.dir=dir; f=push(s,elem);/如果可行将数据入栈 if(f=false)如果返回假，说明栈容量不足 cout<<"栈长不足"i=x;j=y;dir=0;mazexy=-1; elseif (dir < 7) dir+; else ( elem=pop(s); /8个方向都不行，回退 if(elem.x!=NULL) ( i=elem.x; j=elem.y; dir=ele

22、m.dir+1; while(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1);/循环if(s->top=-1)/若是入口，则无通路 cout<<"此迷宫不通" else ( elem.x=x; elem.y=y; elem.dir=dir;/将出口坐标入栈 f=push(s,elem); cout<<"迷宫通路是："<<endl; i=0; while (i <= s->top) ( cout

23、<<"("<<s->stacki.x<<","<<s->stacki.y<<")"/ 显示迷宫通路 if(i!=s->top) cout<<"->"if(i+1)%4=0) cout<<endl; i+； / void draw(int mazeN2,sqstktp *s)在迷宫中绘制出通路 cout<<"逃逸路线为："<<endl; int i,j； elemtype elem; for(i=1;i<=M;i+)将迷宫中全部的-1值回复为0值 for(j=1;j<=N;j+) if(maze