Problem
Rotting Oranges
Medium- graphs
- bfs
- matrix
grid is a tray of oranges. A 0 is an empty cell, a 1 is a fresh orange and a 2 is a rotten one. Every minute, each fresh orange that has a rotten orange directly above, below, left or right of it turns rotten. All of them turn at the same moment, so an orange that rots in one minute starts spreading the rot only in the next.
Return the number of minutes until no fresh orange is left. If some fresh orange can never rot, return -1.
- Input
grid = [[2, 1, 1], [1, 1, 1], [1, 1, 2]]- Output
2- Explanation
the two rotten oranges spread at the same time. In minute 1 the four fresh oranges that touch a rotten one rot, and in minute 2 the remaining three do.
- Input
grid = [[2, 1, 0], [0, 0, 1]]- Output
-1- Explanation
the fresh orange in the bottom-right corner has an empty cell above it and another to its left. The rot in the top row is only diagonal to it, which does not count, so it never reaches that corner.
- Input
grid = [[2, 0], [0, 2]]- Output
0- Explanation
there is no fresh orange, so no time has to pass.
Constraints:
gridhas at least one row, and every row has the same length
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.