# -*- coding:utf-8 -*- from collections import deque   # 引入队列 maze = [    [1,1,1,1,1,1,1,1,1,1],    [1,0,0,1,0,0,0,1,0,1],    [1,0,0,1,0,0,0,1,0,1],    [1,0,0,0,0,1,1,0,0,1],    [1,0,1,1,1,0,0,0,0,1],    [1,0,0,0,1,0,0,0,0,1],    [1,0,1,0,0,0,1,0,0,1],    [1,0,1,1,1,0,1,1,0,1],    [1,1,0,0,0,0,0,0,0,1],    [1,1,1,1,1,1,1,1,1,1] ] # 四个移动方向dirs = [    lambda x,y: (x+1, y),   # 下    lambda x,y: (x-1, y),   # 上    lambda x,y: (x, y-1),   # 左    lambda x,y: (x, y+1)    # 右]  def print_r(path):    """打印路径"""    curNode = path[-1]    # 最后一个节点    realpath = []         # 出去的路径    while curNode[2] != -1:   # 判断最后一个节点的标记是否为-1，如果是-1说明是起始点，如果不是-1就继续查找        realpath.append(curNode[0:2])   # 拿到并添加节点x,y坐标信息        curNode = path[curNode[2]]      # 这里curNode[2]是当前节点的前一步节点的标识：path的下标，因此path[curNode[2]]拿到前一节点     realpath.append(curNode[0:2])       # 在这里curNode[2] == -1，是迷宫起点，将坐标信息加入路径     realpath.reverse()    # 将列表倒序，将前面生成的从后往前的列表变为从前往后    print(realpath)  def maze_path_queue(x1, y1, x2, y2):   # (x1,y1)代表起点；(x2,y2)代表终点    """用队列实现迷宫问题——深度优先搜索"""    queue = deque()   # 创建队列    queue.append((x1, y1, -1))    # 加入起点，第三个参数是记录时谁让它来的，这里起始点设置为-1    path = []   # 保存出队节点    while len(queue) > 0:   # 只有队不空就一直循环        curNode = queue.pop()  # 队首节点出队，并存为当前节点变量        path.append(curNode)   # 添加到path列表        if curNode[0] == x2 and curNode[1] == y2:   # 判断是否找到终点            print_r(path)   # 如果到达终点，打印路径            return True         for dir in dirs:    # 搜索四个方向            nextNode = dir(curNode[0], curNode[1])    # curNode[0],curNode[1]分别是当前节点x、y            if maze[nextNode[0]][nextNode[1]] == 0:   # 如果有路可走                queue.append((nextNode[0], nextNode[1], len(path) - 1))   # 后续节点进队，标记谁让它来的：path最后一个元素的下标                maze[nextNode[0]][nextNode[1]] = 2   # 设置为2，标记为已经走过     else:   # 如果队列为空（当前节点到了死路，节点删除没有新节点加入），没有路        print("没有路")        return False  maze_path_queue(1,1,8,8)