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

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