题目

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

示例 2:

注意:

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

解答一（BFS）

def updateMatrix(matrix: [[int]]) -> [[int]]:
    '''先找出所有的起点（值为零的坐标）；然后应用BFS；所有起点同步执行，每执行一步标上数值'''
    m = len(matrix)
    n = len(matrix[0])
    if not m or not n:
        return [[]]

    queue = [(x, y) for x in range(m) for y in range(n) if matrix[x][y] == 0] # bfs 起点
    visited = set(queue)
    for i, j in queue:
        for next_i, next_j in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= next_i < m and 0 <= next_j < n and (next_i, next_j) not in visited:
                matrix[next_i][next_j] += matrix[i][j] # 利用01矩阵特性（只有01）直接进行加和即可得到距离
                visited.add((next_i, next_j))
                queue.append((next_i, next_j))
    return matrix

原文

https://leetcode-cn.com/explore/learn/card/queue-stack/220/conclusion/892/