Rotting Oranges
Medium · graph traversal
A crate of oranges is laid out as a rectangular grid. Each cell holds one of three numbers:
0: the cell is empty.1: the cell holds a fresh orange.2: the cell holds a rotten orange.
Every minute, each fresh orange that shares an edge (up, down, left or right) with a rotten orange becomes rotten too. All oranges that rot in the same minute do so at the same moment, so an orange that has just turned rotten only starts spreading during the next minute. Empty cells never change and nothing spreads through them.
Return the number of minutes that pass until no fresh orange is left. If the grid has no fresh orange to begin with, return 0. If some fresh orange can never become rotten, return -1. You may change the grid while you work, only the number you return is checked.
Examples
Example 1
Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
Output: 4
The rot reaches the two cells next to the start after 1 minute, and the far corner at the bottom right after 4 minutes.
Example 2
Input: grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
Output: -1
The orange in the bottom left corner only touches empty cells and the grid edge, so the rot never reaches it.
Example 3
Input: grid = [[0, 2]]
Output: 0
There is no fresh orange, so no time has to pass.
Constraints
- 1 <= rows, cols <= 30
- Every cell is 0, 1 or 2.
- All rows have the same length.