542. 01 矩阵

题目

想了两种思路

  1. 0 位置的上下左右是 1， 上下左右中有跟 1 相邻的就是 2，以此类推，从 0 的坐标开始往上下左右四个方向扩散。如果我们把同意个距离的看作是一层，可以用一个队列依次存放每一层的坐标，直至每个坐标都被计算过。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution:
        def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
            m, n = len(matrix), len(matrix[0])
            dist = [[0] * n for _ in range(m)]
            zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
            # 将所有的 0 添加进初始队列中
            q = collections.deque(zeroes_pos)
            seen = set(zeroes_pos)

            # 广度优先搜索
            while q:
                i, j = q.popleft()
                for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                    if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
                        dist[ni][nj] = dist[i][j] + 1
                        q.append((ni, nj))
                        seen.add((ni, nj))

            return dist

  2. 从左上角开往右下角遍历矩阵，当前坐标的距离由左和上两个位置的值确定。遍历一遍后，再反过来从右下角开始往左上角遍历，当前坐标的距离根据右和下两个位置的值确定，比较这两次得出的值中较小的一个即为该点的距离。