Oranges Rotting

orange_rotting.py

from collections import deque

class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        # corner cases
        if not grid or not grid[0]:
            return 0

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

        queue = deque()
        visited = set()

        # init multiple starting vertices
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    # start with depth = 0
                    queue.appendleft((i, j, 0))
                    visited.add((i, j))

        # BFS
        d = 0
        while queue:
            r, c, d = queue.pop()
            for i, j in [[r + 1, c], [r, c + 1], [r - 1, c], [r, c - 1]]:
                # valid neighbours
                if 0 <= i < n and 0 <= j < m:
                    if grid[i][j] == 1 and (i, j) not in visited:
                        queue.appendleft((i, j, d + 1))
                        visited.add((i, j))

        # check if there are still fresh oranges
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1 and (i, j) not in visited:
                    return -1

        return d