Python解题：二进制矩阵中的最短畅通路径

问题描述：

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

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

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

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

解题思路：

本题可以使用广度优先搜索（BFS）来解决。

1. 从起点 (0, 0) 开始，如果起点值为 1，则直接返回 -1。2. 创建一个队列，并将起点加入队列。3. 创建一个二维数组 visited，用于记录已经访问过的位置，初始值为 False。4. 循环遍历队列，直到队列为空： - 从队列中取出一个位置。 - 如果该位置为终点，则返回当前路径长度。 - 获取该位置周围八个方向上的有效位置（在矩阵范围内且值为 0）。 - 对于每个有效位置： - 如果该位置未被访问过： - 将该位置标记为已访问。 - 将该位置加入队列。 - 当前路径长度加 1。5. 如果遍历完队列仍未找到终点，则说明不存在畅通路径，返回 -1。

**Python 代码实现：**pythonfrom collections import deque

def shortestPathBinaryMatrix(grid): n = len(grid) if grid[0][0] == 1 or grid[n-1][n-1] == 1: return -1 directions = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)] queue = deque([(0,0,1)]) # (row, col, path_length) visited = [[False] * n for _ in range(n)] visited[0][0] = True

while queue:        row, col, path_length = queue.popleft()        if row == n - 1 and col == n - 1:            return path_length        for dr, dc in directions:            r, c = row + dr, col + dc            if 0 <= r < n and 0 <= c < n and grid[r][c] == 0 and not visited[r][c]:                visited[r][c] = True                queue.append((r, c, path_length + 1))    return -1

示例grid = [[0,1,0],[1,0,0],[0,0,0]]print(shortestPathBinaryMatrix(grid)) # 输出：4

时间复杂度： O(n^2)。最坏情况下，需要遍历所有的位置。

空间复杂度： O(n^2)。需要使用一个二维数组 visited 来记录已经访问过的位置，以及一个队列存储待访问的位置。