A crate of oranges is laid out as the grid grid. Each cell holds one of three values:
0: the cell is empty;1: the cell holds a fresh orange;2: the cell holds a rotten orange.Rot spreads once a minute. At the end of every minute, each fresh orange that shares a side with a rotten one (the cell above, below, left or right, not diagonal) turns rotten too. Empty cells don't pass rot on.
Return the number of minutes until no fresh orange is left. If some fresh orange can never turn rotten, return -1. If there are no fresh oranges to begin with, the answer is 0.
The rot starts in the top-left corner. The orange at the right end of the middle row has empty cells above it and to its left, so the rot has to reach it the long way: down the second column, along the bottom row, and up. It arrives there at minute 6, and every other orange has rotted by then.
The orange in the top-left corner has only empty cells beside it, so the rot never reaches it.
There is no fresh orange at all, so no time needs to pass.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] is 0, 1 or 2.All rotten oranges spread at the same time, so start one breadth-first search from all of them at once: the oranges that rot in minute k are exactly the search's k-th layer.
6