LeetCode 541. Reverse String II

题目描述

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

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

示例 1：

输入：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

输出：
[[0,0,0],
 [0,1,0],
 [0,0,0]]
示例 2：

输入：
[[0,0,0],
 [0,1,0],
 [1,1,1]]

输出：
[[0,0,0],
 [0,1,0],
 [1,2,1]]

提示：

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

算法

(宽度优先搜索) O(nm)
定义一个队列，初始时将所有 0 元素的坐标进队；定义答案数组 res，0 元素位置的值为 0，其余为 -1。
对这个队列开始进行宽度优先搜索，每次扩展上下左右四个方向，若发现新的位置在 dis 中值为 -1，则更新新位置的答案为当前位置答案加 1。

时间复杂度

宽度优先搜索每个位置仅被遍历一次，故时间复杂度为 O(nm)。

空间复杂度

需要额外的空间存放队列和每个点的距离，故空间复杂度为 O(nm)。

python code

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        if not matrix or not matrix[0]: return matrix
        m = len(matrix)
        n = len(matrix[0])
        res = [[-1]*n for _ in range(m)]
        q = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    res[i][j] = 0
                    q.append([i,j])
        dx = [-1,0,1,0]
        dy = [0,1,0,-1]
        while q:
            tmp = q.pop(0)
            for i in range(4):
                x = dx[i] + tmp[0]
                y = dy[i] + tmp[1]
                if 0 <= x < m and 0 <= y < n and res[x][y] == -1:
                    res[x][y] = res[tmp[0]][tmp[1]] + 1
                    q.append([x,y])
        return res