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 的距离。