c语言实现迷宫问题.

1、数据结构试验一一迷宫问题数据结构试验迷宫问题(一)基本问题1 .问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子 的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行， 迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布.置了许多障碍的通道中寻找出路的问题。本 题设置的迷宫如图1所示。入口图1迷宫示意图迷宫四周设为墙：无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、 北(为了清晰，以下称“上下左右”卜左上角为入口。右下角为出口。迷宫有一个入口，一 个出口。设计程序求解迷宫的一条通路。2 .数据结构设计以一个mXn

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

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

4、上、右、下、左（即 顺时针方向）依次编号为0、1、2、3.其增量数组move 4如图3所示。x ymove4 0 123图2数组move 4(i-1, j)方位0方位示意图如下:方位3(i, j-1)方位1（i,j）（i + 1, j）方位2 图3.方位图通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性 j和一个方向属性di,表示其下一点的位置。如果约定尝试的顺序为上、右、下、 左（即顺时针方向），则每尝试一个方向不通时，di值增1,当d增至4时，表 示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一 条迷宫通路。（1）下面介绍求解迷宫（xi,yj）到终点

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

6、;st top. di=-lwhile (top>-l)栈不空时循环i=st top, i ; j=st top. j ; di=st top. di ; /取栈顶方块 if (i=xe && j=ye) 找到了出口，输出路径printf (迷宫路径如下：n); for (k=0;k<=top;k+)printf ("t (%d, %d) ", st k. i, st k. j);if (k+l)%5=0)每输出每5个方块后换一行printf (n)；)printf Cn，z);return(1); 找到一条路径后返回1)否则，找下一个可走的相邻

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

8、为此，在一个方 块进栈后，将对应的mg数组元素的值改为-1(变为不可走的相邻方块)，当退栈时(表示 该方块没有相邻的可走方块)，将其值恢更0,其算法代码和相应的解释如下：find=0;while (di<4 && fuid=0)找下一个可走方块(di+; switch(di) (case 0:i=sttop .i-l;j=sttop .j ;break:case 1 :i=sttop.i;j=sttop.j+l ;break: case 2:i=sttopi+1 J=sttop.j ;break; case 3:i=sttop .ij=sttop .j-1 ;break;

9、 )if (mgij=0) find=l;找至I下一个可走相邻方块 ) lf(filld=l)找到了下一个可走方块(sttop.di=di;修改原栈顶元素的di值top+；下一个可走方块进栈sttop.i=i;sttop .j=j ;sttop. di=-l; 避免重及走到该方块) else没有路径可走,则退栈mgsttop.i sttop j=0/让该位置变为其他路径可走方块 top-;将该方块退栈) ieturn(0);表示没有可走路径，返回0 (2)求解主程序建立主函数调用上面的算法，将mg和st栈指针定义为全局变量 void main()(mgpath(l,LM,N)；3界面设计设计很

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

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

12、从move数 组中得到从国点出发搜索到的每一个相邻点x=i+movedH.dxy=7j+move dir .dydx dv图7方向位移图图8向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为0改为-1,这既 可以区别该位置是否已经走到过，乂可以与边界值1相区别。当整个搜索过程结 束后可以将所有的-1改回到0,从而恢复迷宫原样。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从(E) 开始，按顺时针对8个方向进行探测，若某个方位上的mazex,y=0,表示可以 通行，则走一步；若mazex,y=l,表示此方向不可通行须换方向再试。直至8 个方向都试过，mazex,y均为1,说

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

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

15、出路径退出循环 )未找到路径(4)输出从入口点到出口点的一条路径。(5)输出标有通路的迷宫图。3 .算法流程图：图9算法流程图4 .程序代码：存define M2 12/*M2*N2为实际使用迷宫数组的大小*/define N2 11define maxlen M2 / 栈长度#include <stdio.h>#iiiclude<iostieam.h>#iiiclude <malloc.h>mt M=M2-2,N=N2-2/M*N 迷宫的大小typedef struct 定义栈元素的类型(int x,y,du;Jelemtype;typedef struc

16、t 定义顺序栈 (elemtype stack niaxlen;int top;Jsqstktp;stnict movedmove定义方向位移数组的元素类型对于存储坐标增量的方向位移数组 nit dx.dy;/void uuniaze(mt maze口N2)初始化迷宫 (mt ijjium;for(i=0,j=0;i<=M+1 ;i+)/ 设置迷宫边界inazeiIj=l;fbr(i=O j=0 J<=N+1 ;j+)mazeij=l;fbr(i=M+l j=O;j<=N+l ;j+)mazeij=l;coutw”原始迷宫为："<<endl;fbr(i=

17、 1 ;i<=M;i+) (for(j=lJ<=Nj+)(num=(800*(i+j)+1500) % 327;根据 MN 的值产生迷宫if (num<150)&&(i!=M|j!=N) mazeij=l;elsemazeij=O;cout«maze i j«M "/显示迷宫 cout«endl;cout«endl;/inimaze/；void inunove(stnict moved move口)初始化方向位移数组/依次为 East, Southeast, south, southwest, west, no

18、rthwest, north, noitheastmove0.dx=0;move0.dy=l ；movel .dx= 1 ;movel.dy= 1;move2.dx=l ;move2.dy=0;move3.dx=l;move3.dy=-l；move 4.dx=0 ;move 4.dy=-l ；move5.dx=-l;move5.dy-=l;move 6.dx=-l ;move 6. dy=O;move7.dx=-l ;move7.dy=l;void inistack(sqstktp *s)/*初始化栈*/(s->top=-l;/*uiistack*/mt push(sqstktp*s,e

19、lemtype x)(if(s->top=maxlen-1) return(false);elses->stack+s->top=x;/*栈不满，执行入栈操作*/ retuin(tiiie); /*push*/ elemtype pop(sqstktp *s)/*栈顶元素出栈*/ (elemtype elem;if(s->top<0)如果栈空，返回空值 elem.x=NULL; elem.y=NULL; elem.dir=NULL; return(elem); elses->top;retuni(s->stacks->top+1 ); 栈不空，返

20、回栈顶元素 /pop/void path(mt niazeN2,stnict moved move,sqstktp *s) 寻找迷宫中的一条通路 (int i,j.du,x,y,f;elemtype elem;i=l;j=l;du=O;niazell=-l; 设为入口处 do (x=i+movedu .dx;W下一步可行的到达点的坐标 y=j+movedu .dy; if(niazexy=O) ( elem.x=i;elem.y=j ;elem.du=du-; f=push(s,elem); 如果可行将数据入栈 if(f=fhlse)如果返回假，说明栈容量不足 coutvv"栈长不足

21、”； i=xj=y;du-O;niazexy=-l;elseif (dir < 7) dir+;else ( elem=pop(s); Z/8个方向都不行，回退 if(elem.x! =NULL) ( i=elem.x; j=elem.y; dii-elem.dir+1;)while(!(s->top=-l)&&(du>=7)|(x=M)&&(y=N)&&(mazexy=-l); 循环 if(s->top=-l)若是入口，则无通路 coutw”此迷宫不通”； else elem.x=x; elem.y=y; elem.du

22、=du;/W 出 I I 坐标入栈 f=push(s,elem);coutw"迷宫通路是："vendl;1=0;while (i <= s->top)cout«”(yvs->stacki.xvv”,yvsdstacki.y<v")”;显示迷宫通路 if(i!=s->top)cout«"->"if(i+l)%4=0) cout«endl;i+；) ) ) llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

23、lllllllllllllivoid draw(iiit mazeN2,sqstktp *s)在迷宫中绘制出通路(coutvv”逃逸路线为："V<endl;mtij;elemtype elem;for(i=l;i<=M;i+)将迷宫中全部的-1值回复:为0值for(j=lj<=Nj-H-)(if(niazeij=-l) mazeij=0;while(s->top>-l)根据栈中元素的坐标，将通路的各个点的值改为8(elem=pop(s);i=elem,xj=elem.y;mazei|j=8;)fbr(i=l;i<=M;i-H-)(fbr(j=lj&

24、lt;=Nj+)(prmtf("%3d",mazei1j);显示已标记通路的迷宫cout«endl;)void main()寻找迷宫通路程序(sqstktp *s;int maze M2 N2;struct moved move8;inmiaze(maze);s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s);inuno ve(move);path(niaze .move, s);cout«endl;diaw(maze,s);5 .运行结果初始化迷宫数组初始化栈初始化方向位移数组寻找迷宫通路绘制作出通路标记的迷

25、宫迷宫通路是：<1.1>>5-2>><2.3>><3.4>><4。5)XS-6)><5.7>><6.8>>逃逸路线为8810Pressa.nycontinue<7.9>一一>C8,8>一一><9,9>><10,9>（三）求所有通路和最短路径的算法1 .源代码（用原题的数据）#iiiclude <stdio.h>frdefine M 5define N 7frdefine MaxSize 100 mt mgM-r

26、lN+l= 1,1,1,1,1,1,1,1,1,0,0,10,0,0/, (1,1,0,0,0,1,1,1), 1,0,0,1,0,0,0,1,/*行数*/*列数*/*栈最多元素个数*/* 一个迷宫，其四周要加上均为1的外框*/1,0,0,0,040,1,(1,1,1,1,14,1,1)；stmctint i;int j;mt di; StackMaxSize.PathMaxSize; /*定义栈和存放最短路径的数组*/hit top=-l;hit count=l;mt iiunlen=MaxSize;void mgpathQ/*栈指针*/*路径数计数*/*最短路径长度*/产路径为:(l,l)

27、->(M-2,N-2)*/*进栈*/mt i,j,di,find,k; top+； Stacktop.i=l; Stacktop.j=l;Stacktop.di=-1 ;mg 1 1 =-1; /* 初始结点进栈 */*栈不空时循环*/i=Stacktop.ij=Stacktop.j;di=Stacktop.di;if(i=M-2 && j=N-2) /*找到了 出口,输出路径*/ (prmtf(H%4d: count-H-);for (k=0:k<=top;k+)printf(,(%d,%d) n,Stackk.i,Stackk.j);if(k+l)%5=0)pn

28、ntf(”nt")； /*输出时每 5 个结点换一行*/)prmtf(HnH);if (top-r l<miiilen)/* 比较找最短路径*/(for (k=0;k<=top;k+)Pathk=Stackk;nuiilen=top-rl;)mgStacktop .1 Stackftop .j=0;/*让该位置变为其他路径可走结点*/top-；i=Stacktop.i;j=Stacktop.j:di=Stacktop.di;)find=0;while (di<4 && find=0) /*找下一个可走结点*/ difswitch(di)case 0:

29、i=Stacktop.i-1 ;j=Stacktop .j;break;case 1 :i=Stacktop.i J=Stacktop.j+l ；break:case 2:i=Stacktop.i+l J=Stacktop.j;break: case 3:i=Stacktop.ij=Stacktop.j-l;break; )if (mgij=O) find=l;)if (find= 1)/*找到了下一个可走结点*/ Stacktop.di=di;/*修改原栈顶元素的di值*7top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1 ;/* /一个可走结点进栈*

30、/ mgij=-l;/*避免重复走到该结点*/) else/*没有路径可走，则退栈*/( mgStacktop.i Stacktop.j=0;/*让该位置变为其他路径可走结点*/top-； ) pnntf("最短路径如下:n"); pnntf("长度:%dn",nuiileii); pnntf(“路径：”)； for (k=O;k<nuiilen;k-H-) priiitf(',(%d,%d) H,Pathk.i,Pathk.j);if(k+l)%5=0)/*输出时每 5 个结点换一行*/ printfCXn"); void ma

31、in() (printf(“迷宫所有路径如下如下 mgpathQ;2求解结果0, 工工<1<4<1<4T<4<1<4>>>>>> > 2 4 2 5 2 5 2 ， * 2 3 2 4 2 4 2 <<<<<< <6 .实验收获及思考这次试验总体来说还是比较简单的，因为几个思考问题都是在基本问题的源代 码上进行改进和补充。有了第一次数据结构编程和测试的经验，这次试验减少了 很多困难，相对来说容易多了。附录基本问题换代码(思考问题源代码在上文中已经全部给出)#define M 4#define N 6frdefine Max