Rotting Oranges

Problem

A grid of cells describes a crate of fruit. Each cell is 0 (empty), 1 (a fresh orange), or 2 (a rotten orange). Every minute, each rotten orange makes all fresh oranges in the four orthogonally adjacent cells rotten. Determine the minimum number of minutes until no fresh orange remains. If some fresh orange can never be reached, return -1.

• The crate has at most 25 rows and 25 columns.
• Cell values are 0, 1, or 2 only.
• If there are no fresh oranges at the start, the answer is 0.

Examples

• grid = [[1,1,2,1],[1,0,1,1],[0,1,1,0]] → 3. Rot spreads out from (0,2); the last fresh orange, at (1,3), turns at minute 3.
• grid = [[2,1,1],[1,1,1],[1,1,1]] → 4. A single rotten corner has to reach the opposite corner, four steps away.
• grid = [[2,1,1],[0,0,1],[1,0,1]] → -1. The orange at (2,0) is walled off by empty cells and can never rot.

Hints

1. Rot spreads one step per minute in all directions from every rotten orange simultaneously. Which traversal explores in order of distance?
2. If you started a search from just one rotten orange, you would get the wrong time. How do you search from all of them at once?
3. Multi-source BFS: enqueue every initially rotten cell at level 0, then expand level by level; the answer is the number of levels needed, and any fresh cell left over means -1.