LeetCode 01矩阵中距离题解

LeetCode 01矩阵中距离题解题目描述给定一个 01 矩阵找到每个 0 到最近的 0 的距离。示例输入mat [[0,0,0],[0,1,0],[1,1,1]]输出[[0,0,0],[0,1,0],[1,2,1]]解题思路方法BFS思路使用 BFS 从所有 0 的位置开始搜索。记录每个 1 到最近的 0 的距离。复杂度分析时间复杂度O(m * n)。空间复杂度O(m * n)。代码实现from collections import deque def update_matrix(mat): m, n len(mat), len(mat[0]) result [[-1] * n for _ in range(m)] queue deque() for i in range(m): for j in range(n): if mat[i][j] 0: result[i][j] 0 queue.append((i, j)) directions [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: i, j queue.popleft() for di, dj in directions: ni, nj i di, j dj if 0 ni m and 0 nj n and result[ni][nj] -1: result[ni][nj] result[i][j] 1 queue.append((ni, nj)) return result # 测试 def test_update_matrix(): mat [[0, 0, 0], [0, 1, 0], [1, 1, 1]] print(update_matrix(mat)) # 输出[[0, 0, 0], [0, 1, 0], [1, 2, 1]] if __name__ __main__: test_update_matrix()总结01矩阵中距离是 BFS 的典型应用从所有 0 的位置开始搜索计算每个 1 到最近的 0 的距离。