数据结构C语言迷宫求解问题.doc

1、1、迷宫求解设计一个迷宫求解程序，要求如下：/ 以M x N表示长方阵表示迷宫，求出一条从入口到出口的通路,或得出没有通路 的结论。“能任意设定的迷宫/ （选作）如果有通路，列出所有通路提示：/ 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：1111111111100100010110010001011000011001101110000110001000011010001001101110110111000000011111111111入口位置：11出口位置：8 8/探索过程可采用如下算法，设定当前位置的初值为入口位置；do 若当前位置可通,则将当前位置插入栈

2、顶;若该位置是出口位置,则结束；否则切换当前位置的东邻方块为新的当前位置;否则，若栈不空且栈顶位置尚有其他方向未经探索,则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相 邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置;/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块出栈至栈空; while （栈不空）；# include #in clude #define MaxSize 32 int a3030;int b3030;int m,n; typedef structint i;int j;int di;Box;typedef structBox

3、dataMaxSize;int top;StackType;bool sereach(int Xzint YJnt XI,int Yl);void main()int X,YzY1,X1;memset(a,Ozsizeof(a);memset(bzO,sizeof(b);/ for()printfCiW输入迷宫的长度和宽度W);while(sca nf(,%d%d,z&m,&n)printf(“请输入迷宫(0表示空地,1表示围墙)n”);for(int i=0;in;i+)for(int j=O;jm;j+)scan f(%d,&aij);lf(aiUJ=l)biU=-l；printf（”请输

4、入迷宫起点的彳靑和列号创）;scan f(,%d%d,z&X,&Y)；printfCiW输入迷宫终点的行号和列号n”); scan f(,%d%d,z&Xl,&Yl)； if(!sereach(X,Y,Xl,Yl)printf(MK迷官没有解!n“); printfCiS輸入迷宫的长度和宽度n“);/ return 0; bool sereach(int X,int Y,int Xl,int Yl)StackType st;int i,j,di,find;st.top=-l;while(aXY!=0)printf(”迷宫起点的行号和列号有错，请重新输入n“); scan f(,%d%d,&X,

5、&Y)；jf(aXY=O)bXY=-l;while(aXlYl!=0)printfC迷宫终点的行号和列号有错，请重新输入n“);scan fC，%d%dH,&Xlz&Yl)；st.top+;st.datast.top.i=X;st.datast.top.j=Y;st.datast.top.di=-l;dofind=O;i=st.datast.top.i;j=st.datast.top.j;di=st.datast.top.dl;while(di=O&i=O&jvm)find=l;if(find = 1)st.datast.top.di=di;st.top+;st.datast.top.l=i;st. data st.top .j=j;st.datast.top.di=-l;find=0;e-se宀bstda5rstrop3stdasstropjNojSLrop; if(H=xl00nHYl) 宀 gntf(糜DD覘暦 fo(jnr kH0jkHSLro