3.3-栈的应用-迷宫求解解析

3.3栈的应用--迷宫求解例四、迷宫【问题描述】

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路。或得出没有通路的结论迷宫用计算机来求解方法其实很简单,就是走遍所有可能的路径,直到找到出口为止,当走到错误的路线的时候,就退回上一个路口交叉点,选择其他方向.这种思维其实用堆栈(stack)完全可以解决例四、迷宫求解通常用的是“穷举求解”的方法

11

112

222

232

133

134

424

125

126

416

315

314

43$$$$$$$$迷宫思路

在设计这个问题时，我考虑到以下几点：

1、迷宫入口和出口的坐标

2、保存迷宫的2维数组

3、获得路径的函数

我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。

在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。

描述:当前点:坐标位置(x,y),可用二维数组实现(seat)记录当前点探索的方向:di如起点为(1,1),先判断东(1),南(2),西(3),北(4),顺时针方向转,判断其邻居是否通,不同的话,邻居转向下一个方向探索,若均不通,则按原路返回,退栈.取栈顶元素,沿下一个方向探索注意:凡走过的也要标记符号:迷宫的分析迷宫设置为一个2维数组，通路为1，不通为0，但是四周为屏障设置一个栈来存储迷宫的路径：记录每个位置的坐标值（x,y),同时将纳入栈中的路径，记录它来自何方，也就是记录它的探测方向编号（东，南，西，北类似于地图的指示，1，2，3，4）通的话就入栈操作：（x,y,di)探测当前坐标位置的所有邻居均不通：出栈，打上脚印，此路不通，不再加入再对栈顶重新探测寻求新的邻居入栈直到达到迷宫出口（有解）或退回到原路的入口（无解）程序流程图开始迷宫求解构建迷宫结束打印路径迷宫算法判断当前结点是否通畅通畅,则记录该点到栈中,并判断是为终点,不为终点的话,继续前行探索不通畅,则后退,换方向访问,到栈空结束设置访问东邻居开始,若其不通,换方向探路邻居访问遍,均不通,退出此结点,取当前栈顶的未访问邻居探路总结:对于一个入栈的节点要记录其位置(x,y),同时记录其探索邻居的方向di(1,2,3,4)记录四个邻居同时对于已经退出的节点标记无需标记其”不通”,只要沿下一个方向转圈就可.迷宫演示见cd中的递归cd迷宫DS-Algo-VC下的第三章算法3.3求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；

do｛

若当前位置可通，

则｛将当前位置插入栈顶；

若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；

｝

否则{

｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：

……若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。实验内容

一个m×n的迷宫，0：畅通，1：障碍，设计一个程序，对任意设定的迷宫，求出从入口到出口的通路。入口：11；出口：68

010110111001101001100111100110011100110101110000

实现提示1．用一种称为广度搜索的算法，将迷宫的入点（1，1）作为第一个出发点，向四周搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置再分别向四周搜索可通行的位置，形成第二层新的出发点，如此进行下去直至到达迷宫的出口点（m，n）为止。实现提示2．为了避免多次检测是否走到边沿，将迷宫周围各镶上一条边，相当于在迷宫的周围布上一圈不通过的的墙。3．为了避免有的点被重复到达，应标志已通过的位置，可以采用一个标志数组来标志已通过了的位置。实现提示4．为了记录搜索过程中到达位置及其出发点，可以建立一个结构体数组，数组的每组元素有三个域x，y，pre，其中分别记录x和y到达位置的行、列坐标，pre记下其出发点在数组中的坐标程序流程图开始迷宫求解构建迷宫结束打印路径注意问题

1．同学们可以先按照给定的迷宫去做，完成的情况下可以将迷宫改成可根据输入变化的任意迷宫。

2．注意数组表示的迷宫下标和现实迷宫下标的不同。

3．跟踪迷宫求解过程中程序的执行情