BFS使用2个队列寻找2维矩阵的最短路径

广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。在寻找二维矩阵的最短路径问题中，BFS通过逐层扩展节点来找到从起点到终点的最短路径。使用两个队列的BFS算法可以有效地处理这个问题。

基础概念

队列：一种先进先出（FIFO）的数据结构。
BFS：从根节点开始，逐层遍历每个节点的所有邻居节点，直到找到目标节点。

优势

简单直观：算法逻辑清晰，易于理解和实现。
保证最短路径：在无权图中，BFS能够保证找到的路径是最短的。

类型

单队列BFS：使用一个队列来存储待访问的节点。
双队列BFS：使用两个队列来优化某些特定情况下的性能。

应用场景

迷宫问题：在二维矩阵中寻找从起点到终点的最短路径。
社交网络分析：查找两个人之间的最短关系链。
网络路由：确定数据包从源到目的地的最短路径。

示例代码

以下是一个使用两个队列的BFS算法来寻找二维矩阵中最短路径的Python示例：

from collections import deque

def shortest_path(matrix, start, end):
    rows, cols = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右, 下, 左, 上
    
    if start == end:
        return 0
    
    queue1 = deque([start])
    queue2 = deque()
    visited = set([start])
    distance = {start: 0}
    
    while queue1 or queue2:
        while queue1:
            current = queue1.popleft()
            for dx, dy in directions:
                next_x, next_y = current[0] + dx, current[1] + dy
                if (0 <= next_x < rows and 0 <= next_y < cols and
                        matrix[next_x][next_y] != 1 and
                        (next_x, next_y) not in visited):
                    if (next_x, next_y) == end:
                        return distance[current] + 1
                    queue2.append((next_x, next_y))
                    visited.add((next_x, next_y))
                    distance[(next_x, next_y)] = distance[current] + 1
        
        queue1, queue2 = queue2, deque()
    
    return -1  # 如果没有找到路径，返回-1

# 示例矩阵
matrix = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
end = (4, 4)
print("最短路径长度:", shortest_path(matrix, start, end))