[数据结构] python 队列解决迷宫问题

例：给一个二维列表（如图所示），表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径。

队列——广度优先搜索

思路：使用队列存储当前正在考虑的节点。从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找直到找到出口。

写代码时分别要考虑以下问题：

1. 当前所在节点四个方向分别为 x+1,y; x-1,y; x,y+1; x,y-1

2. 开辟队列时，要开辟一个三维队列，第三个空间用来记是哪个节点让它来的

3.当前节点是队首节点

4.当走到终点输出队列时，根据是谁让最后一个节点来的来找真实队列

5.可开辟另外一个队列来存储是谁让他来的

6.最后一个节点即队列最后一个元素

1. 没走到终点并且下一节点能走时，把该下一节点加入栈并标记为2，表示走过了

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]
]

# x,y四个方向分别为：x+1,y; x-1,y; x,y+1; x,y-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)
}

# 输出path
def print_r(path):
    curNode = path[-1]  # 当前的最后一个节点就是终点,但是path有很多挑路径，挑能走到终点那条路径
    realpath = []
    while curNode[2] != -1:
        realpath.append(curNode[:2])  # 把节点放到真实路径
        curNode = path[curNode[2]]  # 挑能走到终点那条路
    realpath.append(curNode[0:2])  # -1跳出来了，-1为起点，把起点放进去
    realpath.reverse()  # 把列表倒过来
    for node in realpath:
        print(node)

def maze_path_queue(x1, y1, x2, y2):  # x1,y1代表起点，x2,y2代表终点
    queue = deque()
    queue.append((x1, y1, -1))  # 起始点和谁让它来的
    path = []
    while len(queue) > 0:
        curNode = queue.popleft()  # 当前节点是队首节点，并将队首节点出队
        path.append(curNode)  # 把出队的节点放在另一个列表parh里
        if curNode[0] == x2 and curNode[1] == y2:
            # 终点
            print_r(path)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0], nextNode[1], len(path) - 1))  # curNode让nextNode来的，curNode就是path的最后一个节点
                maze[nextNode[0]][nextNode[1]] = 2  # 标记已经走过
    else:  # 没有一个节点能走
        print('没有路！')
        return False

maze_path_queue(1, 1, 8, 8)

输出为：

(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)