2023年数据结构之迷宫求解实验报告武汉大学

数据结构实验报告——迷宫求解问题实验上机环境：DevC++二、程序设计相关信息（1）实验题目：迷宫求解问题问题描述：实验题3.5改善节中的求解迷宫问题程序,规定输出如图3.14所示的迷宫的所有途径，并求最短途径长度及最短途径。01?.445（2）实验项目组成：本项目由一个原程序mg.cpp及mg.cxc文献组成。（3）实验项目的程序结构：函数调用关系图：mainOQtrurt舛松依monnth/X余杼两加

(4)实验项目包含的函数的功能描述:mg[M+l][N+l]//构造迷宫二维数组，1表达墙不可走方块，0表达通道mg[M+l][N+l]mgpath(intxi,intyi,intxe,intye)〃求解途径为：(xi,yi)—>(xe,ye)//采用顺序栈存储，进栈，回溯,退栈等(5)算法描述:求解迷宫从入口到出口的所有途径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈,并将这个可走发方位保存,且t。p+1,然后试探下一个方块,若下一个方块能走通则继续，否则则回溯到前一个方块，且top-U为记录所有的途径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较I。P值找到一条最短途径并输出。试探途径过程的算法运用了“广度优先搜索遍历”算法。流程图:for循环mg=0(6)实验数据:迷宫数组如下:intmg[M+l][N+l]={{1,1,1,1,1,1}J1,0,0,0,13},{1,0,1,0,0,1},实验结果:{1,0,0,0,1,1),{1,1,0,0,0,1),(1,1,1,1,1,1)}；路径如下：实验结果:1：<1,1><1,2><1,3><2,3><3,3><4,3〉<4,4〉2：<1,1><1,2><1,3><2,3><3,3><3,2X4,2X4,3X4,4>3：<1,1><2,1><3,1><3,2><3,3><4,3><4,4>4：<1,1X2,1X3,1X3,2X4,2><4,3><4,4>最短路径如下：路隹最妞长度：7最短路径路备<12><1,3><2,3><3,3><4,3><4,4>情按任意键继续..<1三、程序代码:#inc1ude<stdio.h>#includc#includc#includc<stdlib.h>#defineM6#define#defineMaxsize100intmg[M+l][N+l]={#includc<stdlib.h>#defineM6U/，l,1,1,1}，{1，0.0,0,1,1),{1,0,1,001},{1,0,0,0,1,1),{1,1,0,0,0,11,{1,1,1,1,1,1});struct(inti；intj;intdi;}Stack[Maxsize],Path[Maxsize];inttop=-l；intcount=1;intmin=Maxsize;intmgpath()(inti,j,di,find,k;top++;Stack[top].i=l;Stack[top].j=1；Stack[top].di=-l;mg[1][1]=-1;Prinif("迷宫所有途径如下：'n")；whi1e(top>—1)i=Stack|top].i;j=Stack[top],j;di=Stack[top].di;if(i==M-2&&j==N-2)prinlf("%4d：",counl++);for(k=0；k<=top;k++){printf("(%d.%d)",Stack[k].i,Stack[k].j);if((k+l)%5==0)printf("\n")；)printfC'\n");if(top+1<min)(for(k=0;k<=top;k++)Path[k]=Stack[k];min=top+1;1mg[Stackftop].i][Stack[top].j]=0;topi=Stack[top].iy=Stack[top].j;di=Stack[top],di;}find=0；while(di<4&&find==0)(di++;switch(di)caseO:i=Stack[top].i-1;j=S(ackftop].j;break；case1：i=Stack[top].i;j=Stack[top].j+l:break;case2:i=Stack[top].i+1;j=Stack[lop],j;break;case3:i=Stack[top].i;j=Stack[top].j-1：break;)if(mg川[j]==0)find=1;}if(find==1)(Stack[top].di=di;top++;Suck[top].i=i;Stackftop].j=j；Stack[top].di=—1;mg[i])else(mg[Stack[topJ.iJ[Stack[(op].j]=0；top)}Printf("\n");printf("最短途径如下:\n")；printf("途径最短长度:％d\n",min)：printf("最短途径途径:\n");for(k=0;k<