使用python求解迷宫问题的三种实现方法

dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量
path=[]              #存找到的路径
 
def mark(maze,pos):  #给迷宫maze的位置pos标"2"表示“倒过了”
    maze[pos[0]][pos[1]]=2
 
def passable(maze,pos): #检查迷宫maze的位置pos是否可通行
    return maze[pos[0]][pos[1]]==0
 
def find_path(maze,pos,end):
    mark(maze,pos)
    if pos==end:
        print(pos,end=" ")  #已到达出口，输出这个位置。成功结束
        path.append(pos)
        return True
    for i in range(4):      #否则按四个方向顺序检查
        nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
        #考虑下一个可能方向
        if passable(maze,nextp):        #不可行的相邻位置不管
            if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束
                print(pos,end=" ")
                path.append(pos)
                return True
    return False
 
def see_path(maze,path):     #使寻找到的路径可视化
    for i,p in enumerate(path):
        if i==0:
            maze[p[0]][p[1]] ="E"
        elif i==len(path)-1:
            maze[p[0]][p[1]]="S"
        else:
            maze[p[0]][p[1]] =3
    print("\n")
    for r in maze:
        for c in r:
            if c==3:
                print('\033[0;31m'+"*"+" "+'\033[0m',end="")
            elif c=="S" or c=="E":
                print('\033[0;34m'+c+" " + '\033[0m', end="")
            elif c==2:
                print('\033[0;32m'+"#"+" "+'\033[0m',end="")
            elif c==1:
                print('\033[0;;40m'+" "*2+'\033[0m',end="")
            else:
                print(" "*2,end="")
        print()
 
if __name__ == '__main__':
    maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
          [1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
          [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
          [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
          [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
          [1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
          [1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
          [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
          [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
          [1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
          [1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
    start=(1,1)
    end=(10,12)
    find_path(maze,start,end)
    see_path(maze,path)

def maze_solver(maze,start,end):
    if start==end:
        print(start)
        return
    st=SStack()
    mark(maze,start)
    st.push((start,0))             #入口和方向0的序对入栈
    while not st.is_empty():      #走不通时回退
        pos,nxt=st.pop()           #取栈顶及其检查方向
        for i in range(nxt,4):     #依次检查未检查方向，算出下一位置
            nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
            if nextp==end:
                print_path(end,pos,st)  #到达出口，打印位置
                return
            if passable(maze,nextp):    #遇到未探索的新位置
                st.push((pos,i+1))      #原位置和下一方向入栈
                mark(maze,nextp)
                st.push((nextp,0))      #新位置入栈
                break                   #退出内层循环，下次迭代将以新栈顶作为当前位置继续
    print("找不到路径")

def maze_solver_queue(maze,start,end):
   path.append(start)
   if start==end:
       print("找到路径")
       return
   qu=SQueue()
   mark(maze,start)
   qu.enqueue(start)                #start位置入队
   while not qu.is_empty():        #还有候选位置
       pos=qu.dequeue()             #取出下一位置
       for i in range(4):           #检查每个方向
           nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
           if passable(maze,nextp): #找到新的探索方向
               if nextp==end:       #是出口，成功
                   print("找到路径")
                   path.append(end)
                   return
               mark(maze,nextp)
               qu.enqueue(nextp)    #新位置入队
               path.append(nextp)
 
   print("未找到路径")