本节利用栈的思想用试探法进行了迷宫一条路径的探索。其中主要的操作是找到下一个空格、如果空格不再可行退回上一个格、每走过一个格子将走过的格子标记为-1防止循环走。

原理如下图：

具体的代码如下：

#走一个任意的5*5迷宫
#mg可以为[[1,1,1,1,1,1],[1,0,1,0,0,1],[1,0,0,1,1,1],[1,0,1,0,0,1],[1,0,0,0,0,1],[1,1,1,1,1,1]]
#5*5的迷宫外面围了一层墙，所以展现为一个6*6的列表
class Box:def __init__(self,i1,j1,di1):#Box是进栈的结点，里面存放着该点的坐标、di表示现在站立的结点走时的方向#注意这里的横纵坐标与平时数学里面的坐标轴不一样self.i=i1#横坐标self.j=j1#纵坐标self.di=di1#方向def mgpath(xi,yi,xe,ye):#xi,yi起点，xe,ye终点global mg#mg是构建的迷宫，用5*5的列表表示st=SqStack()#建立一个链栈，用顺序栈也可以，不过要注意内存问题#dx dy负责辅助建立方向dx=[-1,0,1,0]dy=[0,1,0,-1]e=Box(xi,yi,-1)#e是起点，-1标记在结点中，本题有两个标记，一个在结点中，一个在原来形成的迷宫列表中st.push(e)#每一个走过的结点都进栈，负责记忆走过的路mg[xi][yi]=-1#这个负责在列表里面用-1记录这个结点已经走过了，防止来回走形成死循环while not st.empty():b=st.gettop()#用b标记现在站立的位置if b.i==xe and b.j==ye:#如果站立的位置已经是终点for k in range(len(st.data)):print("["+str(st.data[k].i)+','+str(st.data[k].j)+']',end='')#输出每个结点的横纵坐标值return True#如果是True，到这里就结束啦find =False#如果不是，标记find为Falsedi=b.di#用di标记现在站立的结点要走时的方向while di<3 and find ==False:#用while循环遍历所有方向，从而找到一个方向是空格di+=1#找不到就换一个方向i,j=b.i+dx[di].b.j+dy[di]#找定这个方向之后更新i，j值，这个i、j值是找到空格的坐标if mg[i][j]==0:#用这个判断来判断这个位置是否是空格find =True#找到find就标记为Trueif find:#如果找到了可行的落脚点，就要入栈并把两个标记值标记为-1（一个在栈的结点里，一个在迷宫列表里）b.di=di#最终确定现在站立的结点要走时的方向b1=Box(i,j,-1)#建立要到的结点st.push(b1)#把这个结点入栈mg[i][j]=-1#把标记值标记为-1else:#如果没有找到可行的落脚点，说明这个位置不能落脚，要重新站立的结点mg[b.i][b.j]=0#站立的结点重新标记为0，表示仍然在站立选方向st.pop()#最上面结点出栈，从新寻找新的方向return  False#要不返回没找到，不可行xi,yi=1,1
xe,ye=4,4
print("一条迷宫路径：",end='')
if not mgpath(xi,yi,xe,ye):print("不存在迷宫路径")