How do you solve the rotting oranges problem, and what makes it a multi source BFS?
You start with all the rotten oranges at once, and you spread the rot out one minute at a time. The number of rounds is the number of minutes.
So what makes it a multi source BFS? A normal BFS starts at one place and works outwards from there. This one starts at many places at the same time, because every rotten orange is a source. And that is exactly right, because the rot spreads out from all of them at once.
from collections import deque
def orange_rotting(grid):
rows, cols = len(grid), len(grid[0])
fresh = 0
queue = deque()
for row in range(rows):
for col in range(cols):
if grid[row][col] == 2:
queue.append((row, col))
elif grid[row][col] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)):
row, col = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1
So how does it work? You go through the grid and you put all the rotten oranges in the queue and you count the fresh ones. Then the loop runs. Each round of the loop is one minute. You take the oranges that are rotten now and you look at their four neighbours, and any fresh neighbour becomes rotten and goes into the queue for the next round.
And the line for _ in range(len(queue)) is what makes each round one minute. It fixes the number of oranges to handle at the start of the round, so the new rotten ones that are added are handled in the next round and not this one.
the grid
2 1 1
1 1 0
minute 1 the rot spreads from the 2 to the right and down
minute 2 the fresh oranges next to those become rotten
minute 3 the last fresh orange becomes rotten
the answer is 3
And the answer is minus one when some fresh orange never rots. That happens when there is a fresh orange that is not connected to any rotten one, so the rot can never reach it.
So the rule to remember is this. All the rotten oranges go into the queue at the start, and the number of rounds is the number of minutes.
The last question in this topic shows the version that does not change the grid.