Medium Multi-source BFS Graphs
In plain English: Rotten oranges spread to adjacent fresh oranges each minute. How long until all are rotten?
Multi-source BFS: start by enqueueing all rotten oranges simultaneously. Each BFS level = one minute. Track fresh count; if it reaches 0, return the number of minutes elapsed.
Prompt
In a grid, 0=empty, 1=fresh orange, 2=rotten orange. Each minute, fresh oranges adjacent to rotten ones also rot. Return the minutes until no fresh oranges remain, or -1 if impossible.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def oranges_rotting(grid):
m, n = len(grid), len(grid[0])
# multi-source BFS: all rotten cells enqueued at time 0 so rot spreads simultaneously
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
while queue:
minutes += 1
# process entire current wavefront before advancing the clock
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 2
fresh -= 1
queue.append((nx, ny))
return minutes - 1 if fresh == 0 else -1
# Test: oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) == 4
# Test: oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) == -1