栈应用举例—迷宫问题 迷宫问题:求迷宫中从入口点到出囗点所有可能的简单路径 迷宫模型 墙 通道 2021220
2021/2/20 11 栈应用举例——迷宫问题 迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径 迷宫模型： 入口 (i,j) 出口 墙 通道
所谓的简单路径是指:在求出的任何一条路径上,不能重现某 通道块,否则总有任意多条路径 迷宫问题是许多实际问题的抽象,求解这类问题时,没有现成 的数学公式可以套用,只能采用系统化的试探方法 下面规定 通道用空格“”表示 墙壁用“#”表示 足迹用“0”表示 从入口点到当前立足点间,具有足迹标志的相连的通道块 构成的简单路径叫当前路径 将迷宫模型用二维字符型数组表示: char maze n+1[n+1: 并假定入口为maze[0J0],出口为 mazen][n 考虑一般情况,设maze[ij]为当前立足点,并纳入当前路径 (即印上足迹标志“0”),则从当前立足点继续试探的算法如下 2021220 12
2021/2/20 12 所谓的简单路径是指：在求出的任何一条路径上，不能重现某 一通道块，否则总有任意多条路径 迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成 的数学公式可以套用，只能采用系统化的试探方法。 下面规定： 通道用空格 “ ” 表示 墙壁用 “ # ” 表示 足迹用 “ 0 ” 表示 从入口点到当前立足点间，具有足迹标志的相连的通道块 构成的简单路径叫当前路径 将迷宫模型用二维字符型数组表示： char maze[n+1][n+1]; 并假定入口为 maze[0][0] ，出口为 maze[n][n] 考虑一般情况，设maze[ i ][ j ] 为当前立足点，并纳入当前路径 （即印上足迹标志 “ 0 ” ），则从当前立足点继续试探的算法如下：
if maze[ij是出口 then打印刚找到的一条简单路径,并回溯一步 else if东面的是通道块 then前进一步 else if南面的是通道块 then前进一步 f西面的是通道块 北 then前进一步 else if北面的是通道块 n前进一步 东 else回溯一步 南 2021220
2021/2/20 13 if maze[ i ][ j ] 是出口 then 打印刚找到的一条简单路径，并回溯一步； else if 东面的是通道块 then 前进一步 else if 南面的是通道块 then 前进一步 else if 西面的是通道块 then 前进一步 else if 北面的是通道块 then 前进一步 ( i , j ) 东 else 回溯一步 南 西 北
前进一步:将下一通道块印上“0”作为当前立足点(切换当前立 点),并保存原立足点的信息以便回溯 回溯一步:去掉当前立足点的足迹“0” 把最近的原立足点重新切换为当前立足点; 试探尚未试探过的方向。 上述的活动均需要在迷宫中移动,并且具有方向性,这种活动可 以使用二维数组下标增量技术来实现: 行下标增量dik0 0 0 列下标增量d[k] 方向及其序号k东0南1西2北3 int dil4]={0,10 int dj4]={1,0,-1,0)}; 2021220
2021/2/20 14 前进一步：将下一通道块印上“ 0 ” 作为当前立足点（切换当前立 足 点），并保存原立足点的信息以便回溯。 回溯一步：去掉当前立足点的足迹“ 0 ”; 把最近的原立足点重新切换为当前立足点； 试探尚未试探过的方向。 上述的活动均需要在迷宫中移动，并且具有方向性，这种活动可 以使用二维数组下标增量技术来实现： 行下标增量di[ k ] 列下标增量dj[ k ] 方向及其序号k 东 0 南 1 西 2 北 3 int di[4]={0,1,0,-1}; int dj[4]={1,0,-1,0}; 0 1 1 0 0 －1 －1 0
在上述的规定下 k=0时,maze[i+dk]+dk]为立足点的东面下一块 k=1时,maze[i+dik]+djk]为立足点的南面下一块 k=2时,maze[i+dik]+djk]为立足点的西面下一块 k-3时,maze[i+dik]+djk]为立足点的北面下一块 客体的表示方法设计:从上述的用试探法走迷宫的过程可知,其中 所管理的信息是立足点的信息。可以用三元组(i,j,k)来表 示立足点,其中(i,j)表示立足点的位置信息,k表示立足点 的下一个试探方向。可以将三元组定义成一个结构 struct items( int i,j, k;) 数据的组织方法设计 考察上述用试探法走迷宫的过程: 前进一步时,需要保存原立足点的信息; 回溯一步时,需要取出最近的原立足点的信息,并且遵循 后保存的先取出的原则,即“后进先出”的原则,因此可以用 栈 来记录立足点的信息。 迷宫问题的算法框架 2021220
2021/2/20 15 在上述的规定下： k=0 时，maze[i+di[k]][j+dj[k]] 为立足点的东面下一块； k=1 时，maze[i+di[k]][j+dj[k]] 为立足点的南面下一块； k=2 时，maze[i+di[k]][j+dj[k]] 为立足点的西面下一块； k=3 时，maze[i+di[k]][j+dj[k]] 为立足点的北面下一块； 客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中 所管理的信息是立足点的信息。可以用三元组（ i , j , k ) 来表 示立足点，其中( i , j ) 表示立足点的位置信息，k 表示立足点 的下一个试探方向。可以将三元组定义成一个结构： struct items { int i,j,k; }; 数据的组织方法设计： 考察上述用试探法走迷宫的过程： 前进一步时，需要保存原立足点的信息； 回溯一步时，需要取出最近的原立足点的信息，并且遵循 后保存的先取出的原则，即“后进先出”的原则，因此可以用 栈 来记录立足点的信息。 迷宫问题的算法框架：