Implement oranges_rotting(grid) -> int.
grid is a list of rows of integers: 0 is an empty cell, 1 a fresh orange, 2 a rotten orange. Every minute, each fresh orange that shares a side with a rotten orange becomes rotten. All of these changes happen at once.
Return the number of minutes until no fresh orange is left. Return 0 if there are no fresh oranges at the start, and -1 if some fresh orange can never rot.
oranges_rotting([
[2, 1, 0],
[0, 1, 1],
[1, 0, 2],
])
# -1 (the orange at the bottom-left is cut off)
oranges_rotting([
[2, 1, 1],
[0, 0, 1],
[1, 1, 1],
])
# 6
Grids go up to 200×200, and the rot can snake through the whole grid, so re-scanning every cell once per minute is too slow: aim for O(rows·cols). You may modify grid.
Show hint
Start the search from every rotten orange at once (all at time 0) and expand one minute-layer at a time.