Solutions

# Multi-source BFS.
# graphs

# O(M*N) time | O(M*N) space
def orangesRotting(grid: list[list[int]]) -> int:
    from collections import deque
    ROWS, COLS = len(grid), len(grid[0])

    q = deque()

    # Find all rotten fruits and put them in the queue as starting points
    fresh_count = 0
    visited = set()
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 2:
                q.append((r,c))
                visited.add((r,c))
            elif grid[r][c] == 1:
                fresh_count += 1

    def addCell(r: int, c: int):
        nonlocal fresh_count
        if r<0 or r>=ROWS or c<0 or c>=COLS or \
            (r,c) in visited or grid[r][c] != 1:
            return
        visited.add((r,c))
        q.append((r,c))
        grid[r][c] = 2
        fresh_count -= 1
        
    time = 0
    while q and fresh_count > 0:
        for _ in range(len(q)):
            r,c = q.popleft()
            addCell(r+1, c)
            addCell(r, c+1)
            addCell(r-1, c)
            addCell(r, c-1)
        time += 1

    return time if fresh_count == 0 else -1