542. 01-matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]

  • code
class Solution:
    def updateMatrix(self, matrix):
        m, n = len(matrix), len(matrix and matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != 0:
                    matrix[i][j] = float("inf")
                    if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:
                        matrix[i][j] = matrix[i - 1][j] + 1
                    if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:
                        matrix[i][j] = matrix[i][j - 1] + 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if matrix[i][j] != 0:
                    if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:
                        matrix[i][j] = matrix[i + 1][j] + 1
                    if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:
                        matrix[i][j] = matrix[i][j + 1] + 1
        return matrix
  • code

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        visited = set()
        from collections import deque
        q = deque()
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 0:
                    visited.add((i,j))
                    q.append((i,j))
        
        while q:
            x,y = q.popleft()
            for dirr in [(1,0), (-1,0), (0,1), (0,-1)]:
                newX, newY = x+dirr[0], y+dirr[1]
                if newX >= 0 and newX <= len(mat)-1 and newY >= 0 and newY <= len(mat[0])-1 and (newX, newY) not in visited:
                        mat[newX][newY] = mat[x][y] + 1
                        visited.add((newX, newY))
                        q.append((newX, newY))
        return mat
        
  • code
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        import collections
        m = len(mat)
        n = len(mat[0])

        def findZero(row, col):
            q = deque()
            q.append(((row, col), 0))
            visited = set()
            while q:
                qsize = len(q)
                for _ in range(qsize):
                    rc, d = q.popleft()
                    r, c = rc
                    if r < 0 or r >= m or c < 0 or c >= n:
                        continue
                    if mat[r][c] == 0:
                        return d
                    visited.add((r,c))

                    if (r-1, c) not in visited:
                        q.append(((r-1, c), d+1))
                    if (r+1, c) not in visited:
                        q.append(((r+1, c), d+1))
                    if (r, c-1) not in visited:
                        q.append(((r, c-1), d+1))
                    if (r, c+1) not in visited:
                        q.append(((r, c+1), d+1))
            
        for row in range(m):
            for col in range(n):
                if mat[row][col] == 1:
                    step = findZero(row, col)
                    mat[row][col] = step
        
        return mat