542. 01 Matrix

Link

Multisource bfs

 class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:

        m = len(mat)
        n = len(mat[0])

        dq = deque([])

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dq.append((i,j))
                else:
                    mat[i][j] = 'X'

        s = set()

        k = 1

        while dq:

            lens = len(dq)

            for _ in range(lens):

                x, y = dq.popleft()

                if (x,y) in s:
                    continue
                
                s.add((x,y))

                for i, j in [(0,1),(0,-1),(1,0),(-1,0)]:
                    if not (0<=i+x<m and 0<=j+y<n):
                        continue
                    
                    if mat[i+x][j+y] == 'X':
                        mat[i+x][j+y] = k
                        dq.append((i+x, j+y))

            k += 1

        return mat