资源描述：
《求解迷宫问题c语言,很详细哦.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3
2、所示的迷宫,对应的迷宫数组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}};伪代码：c语言描述如下：voidmgpath()
3、/*路径为:(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)/*找到了出口
4、,输出路径*/ { printf("迷宫路径如下:"); for(k=0;k<=top;k++) { printf("t(%d,%d)",Stack[k].i,Stack[k].j); if((k+1)%5==0) printf(""); } printf(""); return; } find=0; while(di<4&&find==0)/*找下一个可走方块*/
5、 { 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;
6、 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+
7、+; /*下一个可走方块进栈*/ Stack[top].i=i; Stack[top].j=j; Stack[top].di=-1; mg[i][j]=-1;/*避免重复走到该方块*/ } else /*没有路径可走,则退栈*/ { mg[Stack[to
