How Long Until Every Fresh Fruit Spoils
Implement minutesToSpoil
A crate is laid out as a grid. Each cell is empty (0), holds a fresh fruit (1) or holds a spoiled fruit (2). Every minute, every fresh fruit that touches a spoiled fruit on one of its four sides becomes spoiled. Return the minimum number of minutes after which no fresh fruit is left, or -1 if that never happens.
Think of each cell as a node, connected to its four neighbours: the spoilage spreads exactly like a breadth-first search that begins at all the spoiled fruits simultaneously.
Example 1:
Input: grid = [[2,1,0,1],[1,1,1,1],[0,1,1,1]]
Output: 5
Example 2:
Input: grid = [[2,1],[0,0],[1,1]]
Output: -1
Example 3:
Input: grid = [[0,0,2]]
Output: 0
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (empty crate slot), 1 (fresh fruit) or 2 (spoiled fruit) - ●
Every minute, each fresh fruit that is directly above, below, left or right of a spoiled fruit becomes spoiled (spoilage does not pass through empty slots or diagonally) - ●
Return the minimum number of minutes until no fresh fruit remains. If some fresh fruit can never be reached, return -1. If there is no fresh fruit to begin with, return 0 - ●
The grid is a graph in which every cell is a node and cells that share a side are connected
grid =
[[2,1,0,1], [1,1,1,1], [0,1,1,1]]