c语言实现迷宫问题

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

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

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

4、、1、2、3其增量数组move4如图3所示。图2数组move 4(iT, j)方位0方位3（id-1）方位1(j, j+1)方位示意图如下:（i+1, J）方位2图3方位图通路：通路上的每一个点有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: stMaxSize; int top二T;当前方块的行号当前方块的列号/di是下一可走方位的方位号/定义栈/初始化栈指针int i, j, k, di, find; top 卄;/初始方块进栈st top i二xi;sttop j=yi; sttop. di=-l;mgl1=-1;while (top&

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

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

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

9、 (find=l)sttop di=di;top+;/找到了下一个可泄方块/修改原栈顶元素的di值/下一个可走方块进栈sttop i=i;sttop, j二j;sttop di=-l;mgi j二T;/避免重复上到该方块AHA12GAGGAGAGGAFFFFAFAFelse/没有路径可总，则退栈mgsttopL i stLtop. j：二0;/让该位置变为英他路径可定方块 top;/将该方块退栈return(0); 表示没有可泄路径，返回0(2)求解主程序建立主函数调用上面的算法，将mg和st栈指针定义为全局变疑void mainOmgpath(l, 1, M, N);3界面设计设讣很简单的界

10、而，输出路径4运行结果图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 （东北）。但是并非每一个位

11、置都有8个相邻位置。如果 i, j位于边界上，即匸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。于是搜索方向的变化

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

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

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

15、点没有往前的路后退一个节点搜索If （找到了目的地）输出路径退出循环未找到路径(4) 输出从入口点到岀口点的一条路径。(5) 输出标有通路的迷宫图。3. 算法流程图：图9算法流程图4. 程序代码：define M2 12 /*M2*N2为实际使用迷宫数组的大小*/#define N2 11ttdefine maxlen M2 / 栈长度include <stdio. h>#include<iostream h>#include <malloch>int M=M2-2, N=N2-2;/M*N 迷宫的大小typedef struct /上义栈元素的类型int

16、x, y, dir;/elemtype;typedef struct /泄义顺序栈elemtype stack maxlen;int top;sqstktp;struct moved/立义方向位移数组的元素类型对于存储坐标增量的方向位移数组mow int dx, dy;/ /void inimaze (int maze N2)/初始化迷宫int i, j, num;for (i二0, j二0; i<=M+l; i+) /设置迷宫边界mazei j=l;for(1=0, j=O;j<=N+l;j+)mazeij=l;for(i=M+l, j=O;j<=N+l;j+)mazeti

17、j=l;cout«"原始迷宫为:/z«endl;for(i=l;i<=M;i +)for (j=l；j<=N;j+)num= (800*(i+j)+1500) % 327;/根据 MN 的值产生迷宫if (num<150)&&(i!=M Ij!=N)maze Lij=l;elsemazei j二0;cout«maze i j<""/显示迷宫cout«endl;cout«endl;/inimaze/ /void inimove(struct moved moved)/初始化方向

18、位移数组/依次为 East. Southeast> south, southwest, west, northwests north, northeastmove0 dx二0;move _0 dy=l;move1 dx=l;move.l dy=l;move2 dx=l;move2 dy=O;move3 dx=l;move3 dy=-l;move4 dx二0;move4 dy=-l;move5 dx=-l;move5 dy一=1;move6 dx二一1;move6 dy=O;move7 dx=-l;move7 dy=l;/void inistack(sqstktp *s)/*初始化栈*/s

19、->top=-l;/*inistack*/int push(sqstktp*s, elemtype x)if(s->t op=max1en-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;ret

20、urn(s->stacks->top+l);/栈不空，返回栈顶元素 /pop/ /void path(int maze N2, struct moved move, sqstktp *s)/寻找迷宫中的一条通路int i, j, dir, x, y, f; elemtype elem;i=l;j=l;dir=O;maze 1 1二-1;/设1 1为入 口 处dox=i+movedir. dx;/球下一步可行的到达点的坐标y=j+movedir dy;if(mazexyj =0)elem x=i;elem. y二j;elem. dir=dir;f二push(s, elem) ;/如果

21、可行将数拯入栈if(f=false)/如果返回假，说明栈容量不足cout<<"栈长不足"；;j=y;dir=0;mazexyl =-l;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=-l)&&(dir>=7) I ! (x=M)&&(y=N)&&(mazex y =-l);/循环if(s->top=-l)/若

22、是入口，则无通路cout<<"此迷宫不通"；elseelem. x=x; elem. y=y; elem. dir=dir;/将岀口坐标入栈f=push(s, elem);cout«/z迷宫通路是："«endl;i 二0;while (i <= s->top)cout<<" (*«s->stackij. x<<", "«s->stacki y«z/)"/显示迷宫通路 if(i!=s->top)cout<&

23、lt;z，>"if(i+l)%4=0)cout<<endl;i+；/ void draw(int maze N2, sqstktp *s)/在迷宫中绘制出通路cout<<"逃逸路线为："<Xendl;int i, j；elemtype elem;for (i=l; id; i+)/将迷宫中全部的-1值回复为0值for(j=l;j<=N;j+)if (maze iZ j=T) mazeij二0;while(s->top>-l)根据栈中元素的坐标，将通路的各个点的值改为8elem=pop(s);i=elem. x;

24、j=elem. y;mazei j二8;for(i=l;i<=M;i+)for(j=l;j<=N;j+)printf ("%3d",mazei j);显示已标记通路的迷宫cout«endl;void mainO/寻找迷宫通路程序sqstktp *s;int maze M2 N2;struct moved move_8;inimaze(maze) ;/初始化迷宫数组s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s);/初始化栈inimove (move) ;/初始化方向位移数组path (maze, move,

25、 s) ;/寻找迷宫通路/绘制作出通路标记的迷宫cout«endl; draw (maze, s);5. 运行结果10101P：新建文件夹 DebugCpp8方向10 10 110 10 010 0 1010 10 1迷宫通路是，<1.1>一一XI.2>一一><23>一一一一><4.5>><5.&>><5.7>><6.8>><7,9>><8,8>><9.9>><10.9>逃逸路线为S «1

26、£81031910 18 110 0 10 a 1 0 0 110 10 0a 1 0 1 010 100 10 118 101001018188Fi*es：s any keyto仝祁壇重町万冋位務釵纽moue（三）求所有通路和最短路径的算法1.源代码（用原题的数据）#include <stdio. h>/*行数*/*列数*/*栈最多元素个数*/* 一个迷宫，其四周要加上均为1的外框*/#define M 5#define N 7define MaxSize 100 int mgM+lN+l= 1,1,1,1,1,1,1,1,1,0, 0,1,0, 0, 0,1, 1,1

27、,0, 0, 0,1, 1,1, 1,0, 0, to, 0, 0,1,1,0, 0, 0, 0, 0, 0,1, 1,1,1,1,1,1,1,1;structint i;int j;int di;int top=-l;int count=l;int minlen=MaxSize; void mgpath()? StackMaxSize, PathMaxSize; /*定义栈和存放最短路径的数组*/*栈指针*/*路径数计数*/*最短路径长度*/*路径为：(1,1)->(M-2,N-2)/int i, j, di, find, k;top+；/* 进栈 */Stacktop_ i=l;St

28、acktop. j=l;Stack topi. di=-l;mgl 1=-1; /* 初始结点进栈 */ wh订e (top>-l)/*栈不空时循环*/i=Stacktop i;j二Stacktop j;di=Stacktop di; if (i=M-2 && j=N-2) /*找到了出口，输岀路径*/printf C?%4d:"、count+);for (k=0;k<=top;k卄)printf C (%d, %d)”、Stack kJ. i, Stack kJ. j);辻(k+l)%5=0) printf rnt3;/*输出时每5个结点换一行*/pri

29、ntf("n");if (top+l<minlen)/*比较找最短路径*/for (k=0;k<=top;k+)Pathk=Stackk;minlen=top+l;mg Stack Itop. i Stack top, 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-l;j二Stacktop j;break;

30、 case 1:i=Stacktop i;j二Stacktop j+1:break;case 2:i=Stacktop i+1;j二Stacktop j;break; case 3:i二Stacktop i, j二Stacktop j-l;break;if (mgi j=0) find二 1;if (find=l)/*找到了下一个可走结点*/ StacktopL di=di;/*修改原栈顶元素的di值*/top+ ； Stack top. i二 i; Stack top. j=j; Stack top, di 二-1;/* F一个可走结 点进栈*/mgi/*避免重复走到该结点*/else/*没

31、有路径可走，则退栈*/mg Stack top, i Stacktop. j二0;/*让该位It变为其他路径可走结点*/top;printf (”最短路径如下：)；printf ("长度：%dn，z, minlen);printf (，?路径：”)；for (k=0:k<minlen:k+)printf C (%d, %d)", Pathk. i, Pathk. j);if (k+1用5=0) printfCW); /*输岀时每5个结点换一行*/printf("n");void mainOprintf (”迷宫所有路径如下:n");mgp

32、athO ;2求解结果6. 实验收获及思考这次试验总体来说还是比较简单的，因为儿个思考问题都是在基本问题的源代 码上进行改进和补充。有了第一次数据结构编程和测试的经验，这次试验减少了 很多困难，相对来说容易多了。附录基本问题换代码（思考问题源代码在上文中已经全部给出）define M 4#define N 6define MaxSize 100include <stdio. h>int mgM+2N+2=1,1,1,1,1,1,1,1,1,0, 0, to, 0, 0,1,1,1,0, 0, 0,1, 1,1,1,0, 0, to, 0, 0,1 t1,0, 0, 0, 0, 0, 0,1 t1,1,1,1,1,1,1,1;int mgpath(i