542. 01 Matrix

https://leetcode.com/problems/01-matrix/

solution

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        queue = collections.deque()
        m = len(mat)
        n = len(mat[0])
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    queue.append([i, j])
                else:
                    mat[i][j] = '*'        
        
        step = 0
        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        while queue:            
            step += 1
            for i in range(len(queue)):
                this_x, this_y = queue.popleft()
                for step_x, step_y in dirs:
                    new_x = this_x + step_x
                    new_y = this_y + step_y
                    if new_x >=0 and new_x < m and new_y >= 0 and new_y < n and mat[new_x][new_y] == '*':
                        mat[new_x][new_y] = step
                        queue.append([new_x, new_y])
        return mat

时间复杂度：O(mn) 空间复杂度：O(mn)

• 动态规划