Rotting Oranges
A grid holds empty cells, fresh oranges and rotten oranges. Every minute each rotten orange rots its fresh 4-directional neighbours. Return the minimum number of minutes until no fresh orange remains, or -1 if some orange can never rot.
- 1 ≤ m, n ≤ 10
- grid[i][j] ∈ {0, 1, 2}
- Simultaneous spread from many sources
- Time = distance from the nearest rotten orange
- Multi-source BFS, one queue round per minute
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Enqueue every rotten orange as a source at time 0 and count the fresh ones. Run BFS in rounds: for each round pop all currently queued cells, rot each fresh neighbour, decrement the fresh count and enqueue it. The number of rounds that rotted at least one orange is the elapsed time. If fresh oranges remain afterward, return -1.
- Repeatedly scanning the whole grid once per minute is O(m · n · T). Multi-source BFS is the same as adding a virtual super-source connected to all rotten cells.