迷宫问题

迷宫问题求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下:intmg[M+1][N+1]={/*M=10,N=10*/{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};对于迷宫中的每个方块,有上下左右四个方块相邻,如图3.4所示,第i行第j列的当前方块的位置为(i,j),规定上方方块为方位0,顺时针方向递增编号。在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中,为此,将栈定义为:struct{inti;/*当前方块的行号*/intj;/*当前方块的列号*/intdi;/*di是下一可走方位的方位号*/}Stack[MaxSize];/*定义栈*/inttop=-1;/*初始化栈指针*/求解迷宫(1,1)到(M-2,N-2)路径的过程是:先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中方块即为路径。否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。voidmgpath()/*路径为:(1,1)-(M-2,N-2)*/{inti,j,di,find,k;top++;/*初始方块进栈*/Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;while(top-1)/*栈不空时循环*/{i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;if(i==M-2&&j==N-2)/*找到了出口,输出路径*/{printf(迷宫路径如下:\n);for(k=0;k=top;k++){printf(\t(%d,%d),Stack[k].i,Stack[k].j);if((k+1)%5==0)printf(\n);}printf(\n);return;}find=0;while(di4&&find==0)/*找下一个可走方块*/{di++;switch(di){case0:i=Stack[top].i-1;j=Stack[top].j;break;case1:i=Stack[top].i;j=Stack[top].j+1;break;case2:i=Stack[top].i+1;j=Stack[top].j;break;case3:i=Stack[top].i,j=Stack[top].j-1;break;}if(mg[i][j]==0)find=1;}if(find==1)/*找到了下一个可走方块*/{Stack[top].di=di;/*修改原栈顶元素的di值*/top++;/*下一个可走方块进栈*/Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;mg[i][j]=-1;/*避免重复走到该方块*/}else/*没有路径可走,则退栈*/{mg[Stack[top].i][Stack[top].j]=0;/*让该位置变为其他路径可走方块*/top--;}}printf(没有可走路径!\n);}3.2.4队列的应用例子采用队列求解迷宫问题使用一个队列Qu记录走过的方块,该队列的结构如下:struct{inti,j;/*方块的位置*/intpre;/*本路径中上一方块在Qu中的下标*/}Qu[MaxSize];intfront=-1,rear=-1;/*队首指针和队尾指针*/这里使用的队列Qu不是循环队列(因为要利用出队的元素找路径),因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径。搜索从(1,1)到(M-2,N-2)路径的过程是:(1)首先将(1,1)入队;(2)在队列Qu不为空时循环:出队一次(由于不是循环队列,该出队元素仍在队列中),称该出队的方块为当前方块,front为该方块在Qu中的下标。①如果当前方块是出口,则输出路径并结束。②否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块(对应的mg数组值为0),将这些可走的相邻方块均插入到队列Qu中,其pre设置为本搜索路径中上一方块在Qu中的下标值,也就是当前方块的front值,并将相邻方块对应的mg数组值置为-1,以避免回过来重复搜索。(3)若队列为空仍未找到出口,即不存在路径。实际上,本算法的思想是从(1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是将在第8章介绍的图的广度优先搜索方法。voidmgpath()/*搜索路径为:(1,1)-(M-2,N-2)*/{inti,j,find=0,di;rear++;Qu[rear].i=1;Qu[rear].j=1;Qu[rear].pre=-1;/*(1,1)入队*/mg[1][1]=-1;/*将其赋值-1,以避免回过来重复搜索*/while(front=rear&&!find){front++;/*出队,由于不是循环队列,该元素仍在队中*/i=Qu[front].i;j=Qu[front].j;if(i==M-2&&j==N-2)/*找到了出口,输出路径*/{find=1;print(front);/*调用print函数输出路径*/}for(di=0;di3;di++)/*把每个可走的方块插入队列中*/{switch(di){case0:i=Qu[front].i-1;j=Qu[front].j;break;case1:i=Qu[front].i;j=Qu[front].j+1;break;case2:i=Qu[front].i+1;j=Qu[front].j;break;case3:i=Qu[front].i,j=Qu[front].j-1;break;}if(mg[i][j]==0){rear++;/*将该相邻方块插入到队列中*/Qu[rear].i=i;Qu[rear].j=j;Qu[rear].pre=front;/*指向路径中上一方块下标*/mg[i][j]=-1;/*将其赋值-1,以避免重复搜索*/}}}if(!find)printf(不存在路径!\n);}