c语言实现迷宫问题

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

2、块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据,设置一个数组mg如下intmgM+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；在算法中用到的栈采用顺序存储结构，将栈定义为Structinti;/当前方块的行号intj;/当前方块的列号intdi;/di是下一个相邻的可走的方位号stMaxSize;/定义栈inttop=-1/初始化栈3设计运算算法要寻找一条通过迷宫的路径,

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

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

5、块即为路径，其代码和相应解释如下：intmgpath(intxi,intyi,intxe,intye)/求解路径为:(xi,yi)->(xe,ye)(struct(inti;/当前方块的行号intj;/当前方块的列号intdi;/di是下一可走方位的方位号stMaxSize;/定义栈inttop=-1;/初始化栈指针inti,j,k,di,find;top+;/初始方块进栈sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1;while(top>-1)/栈不空时循环(i=sttop.i;j=sttop.j;di=sttop.di;/取栈顶方块if(i=

6、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否则，找下一个可走的相邻方块若不存在这样的路径，说明当前的路径不可能走通，也就是恢复当前方块为0后退栈。若存在这样的方块，则其方位保存在栈顶元素中，并将这个可走的相邻方块进栈(其

7、初始位置设置为-1)求迷宫回溯过程如图4所示.建哉直搜其他路吐S4.£：回浜迂程示.竟图相邻可走方块，若没有这样则从当前方块回溯到前i,j）已经进栈，在试探从前一个方块找到相邻可走方块之后，再从当前方块找在、的方快，说明当前方块不可能是从入口路径到出口路径的一个方块，一个方块，继续从前一个方块找可走的方块。为了保证试探的可走的相邻方块不是已走路径上的方块，如（i+1,j）的下一方块时，又试探道（i,j）,这样会很悲剧的引起死循环，为此，在一个方块进栈后，将对应的mg数组元素的值改为-1（变为不可走的相邻方块），当退栈时（表示该方块没有相邻的可走方块），将其值恢复0,其算法代码和相应的

8、解释如下：find=0;while(di<4&&find=0)找下一个可走方块(di+;switch(di)(case0:i=sttop.i-1;j=sttop.j;break;case1:i=sttop.i;j=sttop.j+1;break;case2:i=sttop.i+1;j=sttop.j;break;case3:i=sttop.i,j=sttop.j-1;break;if(mgij=0)find=1;/找到下一个可走相邻方块if(find=1)找到了下一个可走方块(sttop.di=di;/修改原栈顶元素的di值top+;/下一个可走方块进栈sttop.i=i

9、;sttop.j=j;sttop.di=-1;mgi田=-1;/避免重复走到该方块else/没有路径可走，则退栈(mgsttop.isttop.j=0;/让该位置变为其他路径可走方块top-;/将该方块退栈return(0);/表示没有可走路径，返回0(2)求解主程序建立主函数调用上面的算法，将mg和st栈指针定义为全局变量voidmain()(mgpath(1,1,M,N);3界面设计设计很简单的界面，输出路径4运行结果图5。基本运行结果(二)8个方向的问题1.设计思想(1) 设置一个迷宫节点的数据结构。(2) 建立迷宫图形。（3）对迷宫进行处理找出一条从入口点到出口点的路径o（4）输出该路

10、径。（5）打印通路迷宫图。图6功能结构图当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行歹0序号i,j来表示。而从i,j位置出发可能进行的方向见下图7.如果i,j周围的位置均为0值，则老鼠可以选择这8个位置中的任一个作为它的下一位置。将这8个方向分别记作：E（东）、SE（东南）、S（南）SW（西南）W（西）、NW（西北）、N（北）和NE（东北）。但是并非每一个位置都有8个相邻位置。如果i,j位丁边界上，即i=1,或i=m,或j=1,或j=n,则相邻位置可能是3个或5个为了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为mazem+2,n+2在迷

11、宫行进时，可能有多个行进方向可选，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定i,j的下一步位置的坐标是x,y，并将这8个方位伤的x和y坐标的增量预先放在一个结构数组move8中（见图8）。该数组的每个分量有两个域dx和dy。例如要向东走，只要在j值上加上dy,就可以得到下一步位置的x,y值为i,j+dy。丁是搜索方向的变化只要令方向值dir从0增至7,便可以从move数组中得到从i,j点出发搜索到的每一个相邻点x,y。x=i+movedir.dxy=j+movedir.dy图7方向位移图图8向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为0改为-1,

12、这既可以区别该位置是否已经走到过，乂可以与边界值1相区别。当整个搜索过程结束后可以将所有的-1改回到0,从而恢复迷宫原样。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从(E)开始，按顺时针对8个方向进行探测，若某个方位上的mazex,y=0,表示可以通行，则走一步；若mazex,y=1，表示此方向不可通行须换方向再试。直至8个方向都试过，mazex,y均为1,说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此需要设置一个栈，用来记录所走过的位置和方向(i,j,dir)。当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如乂找到一个行进方向

13、，则把当前位置和新的方向重新进栈，并走到新的位置。如果探测到x=m,y=n,则已经到达迷宫的出口，可以停止检测，输出存在栈中的路径；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如果已经退到迷宫的入口(栈中无元素)，则表示此迷宫无路径可通行。2系统算法(伪代码描述)：(1) 建立迷宫节点的结构类型stack。(2) 入迷宫图形0表示可以通1表示不可以通。用二维数组mazem+2n+2进行存储。数组四周用1表示墙壁，其中入口点(1,1)与出口点(m,n)固定。(3) 函数path()对迷宫进行处理，从入口开始：While(!(s->top=-1)&&(dir>

14、=7)|(x=M)&&(y=N)&&(mazexy=-1)(For(扫描八个可以走的方向)(If(找到一个可以走的方向)(进入栈标志在当前点可以找到一个可以走的方向避免重复选择mazexy=-1不再对当前节点扫描If(八个方向已经被全部扫描过，无可以通的路)(标志当前节点没有往前的路(4) 后退一个节点搜索If(找到了目的地)(输出路径退出循环未找到路径输出从入口点到出口点的一条路径o输出标有通路的迷宫图。3. 算法流程图：图9算法流程图4. 程序代码：#defineM212/*M2*N2为实际使用迷宫数组的大小*/#defineN211#definemaxle

15、nM2/栈长度#include<stdio.h>#include<iostream.h>#include<malloc.h>intM=M2-2,N=N2-2;/M*N迷宫的大小typedefstruct/定义栈元素的类型intx,y,dir;elemtype;typedefstruct/定义顺序栈elemtypestackmaxlen;inttop;sqstktp;structmoved/定义方向位移数组的元素类型对于存储坐标增量的方向位移数组moveintdx,dy;/voidinimaze(intmazeN2)/初始化迷宫inti,j,num;for(i

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

17、t;<""/显示迷宫cout<<endl;cout<<endl;/inimaze/voidinimove(structmovedmove)/初始化方向位移数组(/依次为East,Southeast,south,southwest,west,northwest,north,northeastmove0.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.

18、dy-=1;move6.dx=-1;move6.dy=0;move7.dx=-1;move7.dy=1;/voidinistack(sqstktp*s)/*初始化栈*/(s->top=-1;/*inistack*/intpush(sqstktp*s,elemtypex)(if(s->top=maxlen-1)return(false);else(s->stack+s->top=x;/*栈不满，执行入栈操作*/return(true);/*push*/elemtypepop(sqstktp*s)/*栈顶元素出栈*/(elemtypeelem;if(s->top<

19、;0)如果栈空，返回空值(elem.x=NULL;elem.y=NULL;elem.dir=NULL;return(elem);else(s->top-;栈不空，返回栈顶元素return(s->stacks->top+1);/pop/voidpath(intmazeN2,structmovedmove,sqstktp*s)寻找迷宫中的一条通路(inti,j,dir,x,y,f;elemtypeelem;i=1;j=1;dir=0;maze11=-1;/设11为入口处do(x=i+movedir.dx;/球下一步可行的到达点的坐标y=j+movedir.dy;if(mazexy

20、=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)&&(dir>=7)|(x=M)&&(y=N)&

21、amp;&(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<<”("<<s->stacki.x<<”,"<<s->stacki.y<<”)”;

22、/显示迷宫通路if(i!=s->top)cout<<"->"if(i+1)%4=0)cout<<endl;i+;/voiddraw(intmazeN2,sqstktp*s)/在迷宫中绘制出通路cout<<"逃逸路线为:"<<endl;inti,j;elemtypeelem;for(i=1;i<=M;i+)将迷宫中全部的-1值回复为0值for(j=1;j<=N;j+)if(mazeij=-1)mazeij=0;while(s->top>-1)根据栈中元素的坐标，将通路的各个

23、点的值改为8elem=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;voidmain()/寻找迷宫通路程序sqstktp*s;intmazeM2N2;structmovedmove8;inimaze(maze);初始化迷宫数组s=(sqstktp*)malloc(sizeof(sqstktp);inistack(s);初始化栈inimove(move);初始化方向位移数组5. path(maz

24、e,move,s);/寻找迷宫通路cout<<endl;draw(maze,s);绘制作出通路标记的迷宫运行结果*gCppB|p.exe*191010018010100101191001010R310010L010010X0100展宫通路是，Ct,1>2>><4,5>><£,6>>C5,7>>C6,8>><7,9>>C8,»>>C9,9>>C10,9>逃逸路线为:UNIMIMLUI01S10X01001018±»01i

25、_oia±»s±0n1o1pipift1191301018aiOBiQisi108101018991010108P»*es：s：mnyJceyCoccintinuiie牛增重0-丁万可位移成组皿g（三）求所有通路和最短路径的算法1.源代码（用原题的数据）#include<stdio.h>#defineM5#defineN7#defineMaxSize100intmgM+1N+1=/*行数*/*列数*/*栈取多儿系个数*/*一个迷宫，其四周要加上均为1的外框*/1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0,0,

26、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;structinti;intj;intdi;StackMaxSize,PathMaxSize;/*定义栈和存放最短路径的数组inttop=-1;intcount=1;intminlen=MaxSize;voidmgpath()inti,j,di,find,k;top+;Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;/*初始结点进栈*/while(top>-1)/*栈不空时循环*/i=Stacktop.i;j=Stacktop.j;

27、di=Stacktop.di;if(i=M-2&&j=N-2)/*找到了出口，输出路径*/printf("%4d:",count+);for(k=0;k<=top;k+)printf("(%d,%d)/*栈指针*/*路径数计数*/*最短路径长度*/*路径为：(1,1)->(M-2,N-2)*/*进栈*/if(k+1)%5=0)printf("nt");printf("n");if(top+1<minlen)*/",Stackk.i,Stackk.j);/*输出时每5个结点换一行*/

28、*比较找最短路径*/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)/*让该位置变为其他路径可走结点*/case0:i=Stacktop.i-1;j=Stacktop.j;break;case1:i=Stacktop.i;j=Stacktop.j+1;break;case2:i=Sta

29、cktop.i+1;j=Stacktop.j;break;case3: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(-最短路径如下

30、: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");voidmain()printf(-迷宫所有路径如下:n");mgpath();2求解结果6. 实验收获及思考这次试验总体来说还是比较简单的，因为几个思考问题都是在基本问题的源代码上进行改进和补充。有了第一次数据结构编程和测试的经验，这次试验减少了很多困难，相对来说容易多了。附录基本问题换代码（思考问题源代码在上文中已经全部给出）#defineM4#defineN6#defineMaxSize100#include<stdio.h>intmgM+2N+2=1,1,1,1,