用栈寻找迷宫路径

《用栈寻找迷宫路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用栈寻找迷宫路径李良益2013地球信息科学与技术20155.121.需求分析因为迷宫的特点，走的通或走不通，可以用1和0表示，所以在计算机可以用抽象方法表示迷宫，用如图所示的01图表示迷宫。图中1为通道，0为墙，所求通道为简单通道，即所求路径上不能出现同一通道块。迷宫文件以“maze.txt”的文件名读取。文件内容如下：0000000000011011101001101110100111100110010001111001110111100101110110010001001000111111100000000

2、000在计算机中迷宫0以爱心符号表示，1则用空白，再输入两个坐标，表示起点和终点，横纵坐标从0开始。若坐标不在迷宫之内，则要求重新输入。最后输出带有有路径的迷宫。2.主体设计先考虑程序主要流程：：打开文件“maze.txt”,并读取到二维数组且备份，初始化栈，寻找路径并存入栈中，提取路径，打印备份。程序设计主要有3个要点，即定义位置，栈与栈的元素1）位置的定义typedefstruct{intx;inty;}postype;2)栈的定义typedefstruct{intord;postypeseat;intdi

3、;}SElemType;c)栈元素定义typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;将它们都定义为全局变量：SqStackS={0,0,0};使用的栈SElemTypee={0,{0,0},0};当前位置intmaze[10][10];迷宫postypestart={0,0},end={0,0};开始和结束位置子函数包括四个对栈的操作：StatusInitStack()；初始化栈StatusGetTop()；得到栈顶元素Stat

4、usPush()；元素入栈StatusPop()；元素出栈两个寻找相关路径的操作i：intnext()；修改当先位置为下一个前进位置或者是要测试的位置StatusFindPath()；主函数调用，找到路径存入栈中2.详细设计假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块的位置”则求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入“当前路径”，并继续朝下一位置探索，即切换下一位置为当前位置，如此反复，直到达到出口；若当前位置不可通，则应顺着来向退向前一通道块，然后朝着来向之外的其他方向探索；

5、若该通道块的四周4个方块均不可通，则应从当前路径删除该通道块。所谓下一位置指的是当前位置四周四个方向，假设栈S记录当前路径，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为入栈，“从当前路径上删除前一通道块”的操作即为出栈。求一条路径的算法可简单描述如下：do{若当前位置可通，则{当前位置插入栈顶；若该位置是出口，则结束；否则，切换当前位置的东临块为新的当前位置；}否则，若栈不空且栈顶位置尚有其他位置可以搜索，则设定新的当前位置为沿顺时针方向找到的栈顶位置的下一临块；若栈不空，但栈顶位

6、置四周均不通，则{删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；}}while（栈不空）；在此，尚需说明的一点是，所谓当前位置可通，指的是未经走到过的通道块，即要求该通道块不仅是通道块，而且既不在当前路径上（否则所求路径不是简单路径），而且不是曾经纳入过的通道块，（否则只能在死胡同里转圈）主要功能函数：StatusFindPath(){intn=1;do{if(maze[e.seat.x][e.seat.y]==1){Push();maze[e.seat.x][e.sea

7、t.y]=0;if(e.seat.x==end.x&&e.seat.y==end.y){return0;}else{e.di=0;next(e);}}else{if(S.top!=S.base&&e.di<4){next(e);}if(S.top!=S.base&&e.di==4){maze[e.seat.x][e.seat.y]=0;Pop();Pop();maze[e.seat.x][e.seat.y]=1;}}}while(S.base!=S.top);return0;}修改当前一通道块为下一通道块的函数

8、：intnext(){if(e.di==0){e.di++;e.seat.y++;return0;}if(e.di==1){e.di++;e.seat.x++;e.seat.y--;return0;}if(e.di==2){e.di++;e.seat.y--;e.seat.x--;return0;}if(e.di==3){e.seat.x--;e.seat.y++;if(maze[e.