c语言实现迷宫问题

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

2、素表示一个方块状态，数组元素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 是下一个相邻的可走的方位号stMaxSize;/ 定义栈int top=-1 / 初始化

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

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

5、空时循环一一取栈顶方块（不退栈）若该方块为 出口，输出所有的方块即为路径，其代码和相应解释如下：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>-1)/ 栈不空时循

6、环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 个方块后换一行prin tf("n");prin tf("n");return(1);/找到一条路径后返回1否则，找下一个可走的相邻方块若不存在这样的路径， 说明当前的

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

8、（变为不可走的相邻方块），当退栈时（表示该 方块没有相邻的可走方块），将其值恢复0,其算法代码和相应的解释如下：fin d=0;while (di<4 && fin d=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;/ 找到下一个可走相邻方块if (fin

9、d=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);3界面设计设计很简单的界面，输出路径4 运行结

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

11、即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,y。x=i+movedir.dxy=j+movedir.dyP/I/1f图7方向位移图图8向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为 0改为-1,这既 可以区别该位置是否已经走到过， 又可以与边界值1相区别。当整个搜索过程结 束后可以将所有的-1改回到0,从而恢复迷宫原样。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从(E)开始，按顺时针对8个方向进行探测，若某个方位上的 mazex,y=0,表示可以 通行，则走一步；若 mazex,y=1,表示此方向不可通行须换方向再试。直至8个方向都试过，mazex,y

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

14、(2) 入迷宫图形 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( 找到了目的地 )输出路径退出循环未找到路径(4) 输出从入口点到出口点的一条路径。(5) 输出标有通路的迷宫图。3.算法流程图：开始该点数据入栈dir+回退一步初始化迷宫，显示迷宫初始化方向位移数组寻找迷宫中白勺一条出路出口或入口显示通路图9算法流程图4程序代码：#defi ne M2 12 /*M2*N2 为实际使用迷宫数组的大小*/#defi ne N2 11#defi ne maxle n M2 / 栈长度#i nclude <stdio.h>#in clude<iostream.h>#i nclude <malloc

16、.h>int M=M2-2,N=N2-2;/M*N 迷宫的大小typedef struct /定义栈元素的类型可编辑范本movenortheastint x,y,dir;elemtype;typedef struct / 定义顺序栈elemtype stack maxlen;int top;sqstktp;struct moved/ 定义方向位移数组的元素类型对于存储坐标增量的方向位移数组 int dx,dy;/void inimaze(int mazeN2)/ 初始化迷宫int i,j,num;for(i=0,j=0;i<=M+1;i+)/ 设置迷宫边界 mazeij=1;for

17、(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;/ 根据 MN 的值产生迷宫 if (num<150)&&(i!=M|j!=N)mazeij=1;else mazeij=0;cout<<mazeij<<" "/ 显示迷宫

18、 cout<<endl;cout<<endl;/inimaze / /void inimove(struct moved move)/ 初始化方向位移数组/ 依次为 East， Southeas，t south， southwest， west， northwest， north ， 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.

19、dx=-1;move6.dy=0;move7.dx=-1;move7.dy=1;/void inistack(sqstktp *s) /* 初始化栈 */s->top=-1; /*inistack*/int push(sqstktp*s,elemtype x)if(s->top=maxlen-1) return(false);else s->stack+s->top=x;/* 栈不满，执行入栈操作 */ return(true);/*push*/elemtype pop(sqstktp *s)/* 栈顶元素出栈 */elemtype elem;if(s->top&

20、lt;0) / 如果栈空，返回空值 elem.x=NULL; elem.y=NULL; elem.dir=NULL; return(elem);elses->top-; return(s->stacks->top+1); / 栈不空，返回栈顶元素 /pop/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=i+movedir.dx;/ 球下一步可行的到达点的坐标

21、 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=elem.dir+1;while(!(s->top=-1)&

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

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

24、值回复为 0 值 for(j=1;j<=N;j+) if(mazeij=-1) mazeij=0;while(s->top>-1) / 根据栈中元素的坐标，将通路的 各个点的值改为 8 elem=pop(s); i=elem.x;j=elem.y; mazeij=8; for(i=1;i<=M;i+)for(j=1;j<=N;j+) printf("%3d",mazeij); / 显示已标记通路的迷宫 cout<<endl;void main() / 寻找迷宫通路程序sqstktp *s;int mazeM2N2;struct mo

25、ved move8; inimaze(maze);/ 初始化迷宫数组s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s);/ 初始化栈inimove(move); / 初始化方向位移数组 path(maze,move,s); / 寻找迷宫通路 cout<<endl;draw(maze,s); / 绘制作出通路标记的迷宫5.运行结果C)Det»ugCppS右向.砂已“Is 1« 1用1円闪11 a 1 010 0 101310100 L 01i a i a0 10 1010 10 1k u u 1d 1 id 1 u0 0

26、 10丄0L00辻宫通路是.Cl ” 1 >一XI ”2>If 4,>C4.S>>CS.6>->C5,?>->C6,8>->C?,9>>C8,e>->C9,9>->C10,9>谨逸路线为:» » 1M 1 U L U 1。丄EJ.0 丄0101_ 0 10±0±090 1018± H 011_ 0 1918»±n 1 a1 R H 11«11 a 19 B 1018ataB 101811901 B 1018a

27、 a i0 18 10 8IPr-ess： an51 Jczy to cantinuLe总标壇董町万卩血移隸貂屈疋（三）求所有通路和最短路径的算法1源代码（用原题的数据）#in elude <stdio.h>/*行数*/*列数*/*栈最多元素个数*/* 一个迷宫，其四周要加上均为1的外框*/#defi ne M 5#defi ne N 7#defi ne MaxSize 100 int mgM+1N+1= 1,1,1,1,1,1,1,1,1,0,0,1,000,1,1,1,000,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,

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

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

30、+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;

31、j=Stacktop.j+1;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 /* 没有路径可走 ,则退栈 */mgSta

32、cktop.iStacktop.j=0; /* 让该位置变为其他路径可走结点 */ top-;printf(" 最短路径如下 :n");printf(" 长度 : %dn",minlen);printf(" 路径 : ");for (k=0;k<minlen;k+)printf("(%d,%d) ",Pathk.i,Pathk.j);if (k+1)%5=0) printf("nt");/* 输出时每 5 个结点换一行 */printf("n");void main()

33、printf(" 迷宫所有路径如下 :n");mgpath();2 求解结果6实验收获及思考这次试验总体来说还是比较简单的，因为几个思考问题都是在基本问题的源代 码上进行改进和补充。有了第一次数据结构编程和测试的经验，这次试验减少了 很多困难，相对来说容易多了。附录基本问题换代码（思考问题源代码在上文中已经全部给出）#defi ne M 4#defi ne N 6#defi ne MaxSize 100#i nclude <stdio.h>int mgM+2N+2=1,1,1,1,1,1,1,1,1,0,0,1,000,1,可编辑范本1,1,0,0,0,1,1,1,1,0,0,1