《c语言实现迷宫问题》由会员分享，可在线阅读，更多相关《c语言实现迷宫问题（22页珍藏版）》请在金锄头文库上搜索。
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 个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、
4、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)/ 栈不空时循环i=sttop.i
6、;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否则，找下一个可走的相邻方块若不存在这样的路径， 说明当前的路径不可能 走通，也就是恢复当前方块为0后退栈。若存在这样的方块，则其方位保存在栈 顶元素中，并将这个可走的相邻方块进栈（其初始位置设置为 -
7、1）求迷宫回溯过程如图4所示毎亠迷肓回，氏过程示童图从前一个方块找到相邻可走方块之后,再从当前方块找在、相邻可走方块，若没有这样的方快，说明当前方块不可能是从入口路径到出口路径的一个方块, 一个方块，继续从前一个方块找可走的方块。则从当前方块回溯到前为了保证试探的可走的相邻方块不是已走路径上的方块，如（i,j）已经进栈，在试探（i+1，j）的下一方块时，又试探道（i，j），这样会很悲剧的引起死循环，为此，在一个方块进栈后，将对应的mg数组元素的值改为-1（变为不可走的相邻方块），当退栈时（表示该 方块没有相邻的可走方块），将其值恢复0,其算法代码和相应的解释如下：fin d=0;while (ditop=-1)&(dir=7)|(x=M)&(y=N)&(mazexy=-1)For(扫描八个可以走的方向)If(找到一个可以走的方向)进入栈 标志在当前点可以找到一个可以走的方向 避免重复选择 mazexy=-1不再对当前节点扫描If( 八个方向已经被全部扫描过，无可以通的路 )标志当前节点没有往前的路 后退一个节点搜索If( 找到了目的地 )输出路径退出循环未找到路径(4) 输出从入口点到出口点的一条路径。(5) 输出标有通路的迷宫图。3.算法流程图：开始该点数据入栈dir+回退一步初始化迷宫，显示迷
