[数据结构与算法]栈求解迷宫问题（python）

迷宫问题通常是一个简单路径的问题，采用枚举法找到所有出口

准备：

①构造一个box类储存迷宫方块。

class box:
    def __init__(self,i1,j1,di1):
      self.i = i1
      self.j = j1
      self.di = di1 

②构建线性栈。

class SqStack:
    def __init__(self):
        self.data = []
    def empty(self):
        if len(self.data) == 0:
            return True
        return False
    def push(self,e):
        self.data.append(e)
    def pop(self):
        assert not self.empty()
        return self.data.pop()
    def gettop(self):
        assert not self.empty()
        return self.data[-1]
st = SqStack()

算法流程

? ①取栈顶方块（若栈顶方块为出口，输出栈中的所有方块为一条路径）。

? ②若栈顶方块不是出口取栈顶方块的下一个方位即 $i=b.i+dx[di]$ ,$j=b.j+dy[dj]$试探相邻方块是否可走。

e = box(xi,yi,-1)
st.push(e)
b = st.gettop()
dx = [-1,0,1,0]
dy = [0,1,0,-1]
flag = False
di = b.di
while di < 3 and not flag:
    di+=1
    i = b.i + dx[di]
    j = b.j + dy[di]
    if not mg[i][j]:
        flag = True

? ③若找到b的可走相邻方块则则走到相邻方块$(i,j)$操作为先将原方块的di值置为找到的di然后将下一个方块的$(i,j)$进栈（其初始方位设为-1）。

if flag:
    b.di = di
    b1 = box(i,j,-1)
    st.push(b1)

? ④若b方块找不到可走的相邻方块，说明当前路径不可能走通b方块不会是迷宫路径上的方块，则原路退回。

else:
    st.pop()
    mg[b.i][b.j] = 0

为避免死循环一般将走过的方块置为$?1$退栈之后将该方块重新置为$0$。

找到一条路径

class Box:
    def __init__(self,i1,j1,di1):
        self.i = i1
        self.j = j1
        self.di = di1
from SqStack import SqStack
def mgpath(xi,yi,xe,ye):
    global mg
    st = SqStack()
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    e = Box(xi,yi,-1)
    st.push(e)
    while not st.empty():
        b = st.gettop()
        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
        find = False
        di = b.di
        while di < 3 and find == False:
            di+=1
            i,j = b.i+dx[di],b.j+dy[di]
            if mg[i][j]==0:
                find = True
        if find:
            b.di = di
            b1 = Box(i,j,-1)
            st.push(b1)
            mg[i][j] = -1
        else:
            mg[b.i][b.j] = 0
            st.pop()
    return False

但该算法只能找到一条路径这条路径有可能是最长的，也有可能是最短的。因为最初在规定方位时默认上方为第一次枚举的对象。

故对代码做如下修改(在找到一条路径之后不返回而是将该方块退栈继续寻找下一个方位并且设立一个全局变量记录简单路径的数量)。

if b.i == xe and b.j == ye:
    cnt+=1
     for k in range(len(st.data)):
            print("["+str(st.data[k].i)+','+str(st.data[k].j)+']',end = ' ')
     print()
    b = st.pop()
    mg[b.i][b.j] = 0