[LeetCode] 542. 01 Matrix

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

Start from all '0' cells and use BFS to find the shortest distance to '1' cells.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        ROW = len(mat)
        COLUMN = len(mat[0])
        
        result = [[ROW*COLUMN] * COLUMN for _ in range(ROW)]
        queue = deque([])
        
        for y in range(ROW):
            for x in range(COLUMN):
                if mat[y][x] == 0:
                    result[y][x] = 0
                    queue.append((y, x))
        
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                y, x= queue.popleft()

                for dy, dx in [(0,1), (0,-1), (1,0), (-1,0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN:
                        if step > result[ny][nx]:
                            continue

                        result[ny][nx] = step
                        queue.append((ny, nx))
            
            step += 1
            
        return result