994

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        step = 0
        q = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    q.append((i, j, step))

        while q:
            x, y, step = q.pop(0)
            for xp, yp in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                if 0 <= xp < len(grid) and 0 <= yp < len(grid[0]):
                    if grid[xp][yp] == 1:
                        q.append((xp, yp, step + 1))
                        grid[xp][yp] = 2


        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    return -1

        return step