数据结构之队列求解迷宫最短路径问题

上一篇文章介绍了用栈结构解迷宫问题的方法，虽然能找到走出迷宫的路径，但很显然不是最优路径。本文将进一步介绍用队列，来求解迷宫的最短路径问题。

代码示例

1、迷宫结构和方向函数

maze = [
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 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, 0, 0],
]

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y - 1),
]

2、队列查找路径

from collections import deque

def search_path(x1, y1, x2, y2):
    init_node = (x1, y1, -1)
    queue = deque([init_node])
    # 记录尝试过的节点和来源节点id
    node_list = []
    # 防止重复走到起点
    maze[y1][x1] = 2

    while len(queue) > 0:
        print(queue)
        cur_node = queue.popleft()
        cur_x, cur_y, _ = cur_node
        # 记录走过的路径
        node_list.append(cur_node)
        # 判断结束条件
        if cur_x == x2 and cur_y == y2:
            # 回溯最优路径
            return analyse_path(node_list)
        for dir in dirs:
            next_x, next_y = dir(cur_x, cur_y)
            if 0 <= next_x < len(maze[0]) and 0 <= next_y < len(maze):
                if maze[next_y][next_x] == 0:
                    # 标记该位置已尝试过
                    maze[next_y][next_x] = 2
                    # 最后一位表示来源
                    queue.append((next_x, next_y, len(node_list) - 1))

3、从终点向前回溯，找最短路径

def analyse_path(node_list):
    x, y, idx = node_list[-1]
    best_path = [(x, y)]
    while idx != -1:
        x, y, idx = node_list[idx]
        best_path.append((x, y))
    return best_path[::-1]

4、调用函数

path = search_path(0, 0, 9, 9)
print(path)