二进制矩阵最短畅通路径 - BFS 解法

二进制矩阵最短畅通路径 - BFS 解法

给定一个 n x n 的二进制矩阵 grid，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1。

二进制矩阵中的畅通路径是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

1. 路径途经的所有单元格的值都是 0。
2. 路径中所有相邻的单元格应当在 8 个方向之一上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度是该路径途经的单元格总数。

解法：BFS

可以使用 BFS 在矩阵中寻找最短路径。首先将起点 (0, 0) 加入队列，然后不断从队列中取出第一个元素，向其相邻的 8 个方向扩展，并将扩展出的元素加入队列中。为了避免重复扩展同一个位置，我们可以将已经扩展过的位置标记为 1，表示不可再次访问。

时间复杂度：O(n^2)

空间复杂度：O(n^2)

Python 代码

def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    
    queue = [(0, 0, 1)]  # (row, col, distance)
    visited = set([(0, 0)])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
    
    while queue:
        row, col, distance = queue.pop(0)
        if row == n - 1 and col == n - 1:
            return distance
        
        for dx, dy in directions:
            new_row = row + dx
            new_col = col + dy
            if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, distance + 1))
    
    return -1