LeetCode 542. 01 矩阵

注意:

• 给定矩阵的元素个数不超过 10000。
• 给定矩阵中至少有一个元素是 0。
• 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思路：广度优先搜索

可以从 0 的位置开始进行广度优先搜索。

将 0 视为源点，将其都入队，各个 0 向 1 扩散（在这里每个 1 都是被离它最近的 0 扩散到的）。

扩散的时候要注意，在返回的矩阵中，可以在对应的坐标中设置距离值，同时标记是否访问过。需要注意的是其中 0 元素距离为 0，在构建返回矩阵时，设默认初始值为 0，这个时候，可以直接将源点 0 放入已标记部分。

具体看下面代码实现。

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
 m, n = len(matrix), len(matrix[0])

 # 构建返回矩阵
 ans = [[0] * n for _ in range(m)]
 # 先找所有源点 0 的位置
 zero = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
 # 将所有源点 0 入队列
 from collections import deque
 queue = deque(zero)
 # 标记
 # 这里将源点 0 的位置加入标记
 # 是因为源点 0 的距离就是 0
 # 可不做变化，返回矩阵默认初始值为 0
 sign = set(queue)

 # 需扩散的四个方位
 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

 while queue:
     # 出队列，进行扩散
     i, j = queue.popleft()
     for di, dj in directions:
  ni, nj = i + di, j + dj
  if 0<=ni
实现结果


以上就是使用广度优先搜索的方法，找出源点 0 的位置进行扩散，进而解决《542. 01 矩阵》的主要内容，需要注意的是扩散的同时，需要标记哪部分已经扩散到的。