You're given a grid where each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange next to a rotten one (up, down, left or right) becomes rotten.
Return the minimum number of minutes until no fresh orange remains. If that can never happen, return -1.
Examples
Example 1
- Input
- grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
- Output
- 4
Example 2
- Input
- grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
- Output
- -1
- Why
- The orange in the bottom-left corner is never reached.
Example 3
- Input
- grid = [[0, 2]]
- Output
- 0
- Why
- There are no fresh oranges to begin with.
Constraints
1 <= grid.length, grid[i].length <= 10grid[i][j]is0,1or2.