Rotting Oranges

A grid holds three kinds of cell: 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, each rotten orange rots the fresh oranges directly above, below, left and right of it — diagonals do not count.

• Goal: the minutes until nothing fresh is left, or -1 if that never happens (LeetCode 994).
• Input: [[2,1,1],[1,1,0],[0,1,1]]. Output: 4.
• Input: [[2,1,1],[0,1,1],[1,0,1]]. Output: -1 — the orange at (2, 0) has only empty cells beside it.
• Input: [[0,2]]. Output: 0 — nothing is fresh, so no time has to pass.

Every rotten orange spreads during the same minute, which is what makes this a multi-source BFS rather than a search from one starting point.

One scan to set up, then one pass of the queue per minute.

1. Scan once. Put every rotten orange in the queue and count the fresh ones. Both facts come out of the same pass.
2. Answer the easy case. No fresh oranges means no time has to pass: return 0 before the loop.
3. One minute per pass. Read the queue's size, then dequeue exactly that many oranges. Those are the ones that were rotten when the minute began, so everything they rot turns at the same time.
4. Rot the neighbours. For each of the four directions, a cell that is on the grid and still 1 becomes 2, decreases the fresh count, and joins the queue for the next minute.
5. Decide. When the queue drains, fresh == 0 means the answer is the minute count; anything left fresh could never be reached, so the answer is -1.

Why the fresh count and not the grid. Checking "is anything still fresh" by rescanning the grid each minute would make the method quadratic in the cell count. One integer, decremented as each orange turns, answers the same question in O(1).

The opening scan is stepped through cell by cell, because that is where both the queue and the fresh count come from. Then each minute is one pass: every orange that was rotten when the minute began is dequeued, and the ones it rots are stamped with the minute they turned. Try Two sources, where rot spreads from both corners at once and the middle turns sooner than either could manage alone.