c语言实现迷宫问题

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

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是下一个相邻的可走的方位号stMaxSize;/定

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

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

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

6、top>-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 所示3/19从前一个方块找到相邻可走方块之后，再从当前方块找在、相邻可走方块， 若没有这样的方快， 说明当前方块不可能是从入口路径到出口路径的一个方块， 则从当前方块回溯到前一个方块，继续从前一个方块找可走的方块。为了保证试探的可走的相邻方块不是已走路径上的方块，如（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

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

10、面，输出路径4 运行结果图 5。基本运行结果（二） 8 个方向的问题1.设计思想(1)设置一个迷宫节点的数据结构。(2)建立迷宫图形。5/19(3)对迷宫进行处理找出一条从入口点到出口点的路径。(4)输出该路径。(5)打印通路迷宫图。初始化迷宫通过随机方法设置迷宫布局建立并输出迷宫原图搜索迷宫通路输出迷宫通路及路线图结束图 6 功能结构图当迷宫采用二维数组表示时， 老鼠在迷宫任一时刻的位置可由数组的行列序号 i，j 来表示。而从 i,j 位置出发可能进行的方向见下图 7.如果 i,j 周围的位置均为 0 值，则老鼠可以选择这 8 个位置中的任一个作为它的下一位置。将这 8 个方向分别记作： E

11、（东）、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 在迷宫行进时，可能有多个行进方向可选，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定 i,j 的下一步位置的坐标是 x,y ，并将这 8 个方位伤的 x 和 y 坐标的增量预先放在一个结构数组 move8 中

12、（见图 8）。该数组的每个分量有两个域 dx 和 dy。6/19例如 要向东走，只要在 j 值上加上 dy，就可以得到下一步位置的 x,y 值为 i,j+dy 。于是搜索方向的变化只要令方向值 dir 从 0 增至 7，便可以从 move 数组中得到从 i,j 点出发搜索到的每一个相邻点 x,y 。x=i+movedir.dxy=j+movedir.dydxdy图 7 方向位移图图 8 向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为 0 改为 -1，这既可以区别该位置是否已经走到过， 又可以与边界值 1 相区别。当整个搜索过程结束后可以将所有的 -1 改回到 0，从而恢复迷宫原样

13、。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从（ E）开始，按顺时针对 8 个方向进行探测， 若某个方位上的 mazex,y=0 ，表示可以通行，则走一步；若 mazex,y=1 ，表示此方向不可通行须换方向再试。直至 8 个方向都试过， mazex,y 均为 1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。 为此需要设置一个栈， 用来记录所走过的位置和方向（ i ，j， dir）。当退回一步时， 就从栈中退出一个元素， 以便在上一个位置的下一个方向上探测，如又找到一个行进方向， 则把当前位置和新的方向重新进栈， 并走到新的位置。如果探测到 x=m，y=n

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

15、)&&(mazexy=-1)For(扫描八个可以走的方向 )If( 找到一个可以走的方向 )进入栈标志在当前点可以找到一个可以走的方向避免重复选择 mazexy=-1不再对当前节点扫描If( 八个方向已经被全部扫描过，无可以通的路)标志当前节点没有往前的路后退一个节点搜索If( 找到了目的地 )输出路径退出循环8/19未找到路径(4)输出从入口点到出口点的一条路径。(5)输出标有通路的迷宫图。3.算法流程图：开始初始化迷宫，显示迷宫初始化方向位移数组寻找迷宫中的一条出路dir>=7 或栈空While 栈不空且 dir<7do设 1，1 为出口FFIf mazexy=

16、0elseIfTT该点数据入栈dir+回退一步出口或入口显示通路结束图 9 算法流程图9/194.程序代码：#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/#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 /定义顺序栈elemtyp

17、e stack maxlen;int top;sqstktp;struct moved/ 定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move int dx,dy;/void inimaze(int mazeN2)/初始化迷宫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<=

18、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<<""/ 显示迷宫cout<<endl;10/19cout<<endl;/inimaze/void inimove(struct moved move)/初始化方向位移数组/ 依次为 East， Southeast， south， southwest， wes

19、t， 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;/void inistack(sqstktp *s)/* 初始化栈 */s->top=-1;/*inistack*/int push(sqstktp*s,elemty

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

21、p/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 为入口处dox=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<<" 栈长不足 "

22、i=x;j=y;dir=0;mazexy=-1;elseif (dir < 7)dir+;elseelem=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)&&(mazexy=-1); / 循环 if(s->top=-1)/ 若是入口，则无通路cout<<" 此迷宫不通 "elseelem.x=x;elem.y=y;elem

23、.dir=dir;/ 将出口坐标入栈f=push(s,elem);cout<<" 迷宫通路是："<<endl;i=0;while (i <= s->top)12/19cout<<"("<<s->stacki.x<<","<<s->stacki.y<<")"/显示迷宫通路if(i!=s->top)cout<<"->"if(i+1)%4=0)cout<<en

24、dl;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(mazeij=-1)mazeij=0;while(s->top>-1)/ 根据栈中元素的坐标，将通路的各个点的值改为8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i<=M;i+)fo

25、r(j=1;j<=N;j+)printf("%3d",mazeij);/ 显示已标记通路的迷宫cout<<endl;void main()/ 寻找迷宫通路程序sqstktp *s;int mazeM2N2;struct moved move8;13/19inimaze(maze);/ 初始化迷宫数组s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s);/初始化栈inimove(move);/ 初始化方向位移数组path(maze,move,s);/ 寻找迷宫通路cout<<endl;draw(maze,

26、s);/ 绘制作出通路标记的迷宫5.运行结果（三）求所有通路和最短路径的算法1.源代码（用原题的数据）#include <stdio.h>#define M 5/* 行数 */#define N 7/* 列数 */#define MaxSize 100/* 栈最多元素个数*/int mgM+1N+1=/* 一个迷宫 ,其四周要加上均为1 的外框 */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,14/191,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1;structint i;int j

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

28、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+1<minlen)/* 比较找最短路径*/for (k=0;k<=top;

29、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)15/19case 0:i=Stacktop.i-1;j=Stacktop.j;break;case 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=St

30、acktop.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(" 最

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