Many starting points at once
Start the ripple from every source together, to see how long something takes to spread across a grid. About 14 minutes.
The fruit that spreads
A tray of oranges has some rotten ones. Each minute, every fresh orange next to a rotten one rots too. How many minutes until none are fresh?
Those rotten oranges all start spreading at the same moment, so don't run a search from each one. Put all of them in the line before you begin. The first ring is everything one minute from the nearest rotten orange, the second ring is two minutes, and so on. The number of rings you need is the answer.
queue = deque() queue.append((r, c)) # every source first
- fresh
- 9
- minute
- 0
One rotten orange at the bottom-left, and nine fresh ones. Minute 0.
Counting minutes
To count minutes, handle the line one full ring at a time. At the start of a minute, note how many cells are in the line. Process exactly that many. Anything they add belongs to the next minute.
Count a minute only if something rotted during it. If any orange is still fresh when the line empties, a wall of empty spaces blocked the spread, so the answer is -1. If none were fresh to begin with, the answer is 0.
minutes += 1
for _ in range(len(queue)):
pass # one whole roundA fresh orange is surrounded by empty spaces and never touches a rotten orange. What should the answer be?
- A-1, because it can never rot
- B0, because nothing is happening near it
- CA very large number of minutes
Show the answer
-1, because it can never rot. The line empties with a fresh orange left, so the spread cannot finish.
Time for the rot to spread
trays is a grid. A cell holds 0 for an empty space, 1 for a fresh orange, or 2 for a rotten orange. Every minute, each fresh orange that is directly next to a rotten one (up, down, left or right) becomes rotten. Return the number of minutes until no fresh orange is left, or -1 if that never happens. If there are no fresh oranges at the start, the answer is 0.
trays = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] → 4
1 ≤ rows, columns ≤ 20 · each cell is 0, 1 or 2