Leetcode 1036 Solution

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        q = collections.deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j))

        step = -1 if q else 0
        while q:
            directions = [
                (-1, 0),
                (1, 0),
                (0, -1),
                (0, 1),
            ]

            s = len(q)
            if s == 0:
                break

            step += 1
            for _ in range(s):
                i, j = q.popleft()

                for di, dj in directions:
                    neigh_i = i + di
                    neigh_j = j + dj

                    if 0 <= neigh_i < m and 0 <= neigh_j < n and grid[neigh_i][neigh_j] == 1:
                        q.append((neigh_i, neigh_j))
                        grid[neigh_i][neigh_j] = 2

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

        return step