Graphs Fewest steps with BFS
442. Rotting Oranges
You are given a crate of oranges as a grid of integers, grid, with m rows and n columns. 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.
Every minute, each fresh orange that is next to a rotten orange, up, down, left or right, becomes rotten. All of them rot at the same time.
Return the number of minutes until no fresh orange is left. If some fresh orange can never rot, return
-1.
Example 1
Input: grid = [[2, 1, 1, 0], [1, 1, 0, 1], [0, 1, 1, 2]]
2Explanation: In minute 1, the four fresh oranges next to the two rotten ones rot. In minute 2, the three fresh oranges left rot, because each of them now touches a rotten one.
Example 2
Input: grid = [[2, 1, 0], [0, 0, 1]]
-1Explanation: The orange in the bottom-right corner has only empty cells beside it, so it never rots.
Example 3
Input: grid = [[2, 1, 1], [0, 0, 1], [1, 1, 1]]
6Explanation: The rot cannot cross the empty cells, so it goes round them, one orange a minute. The orange in the bottom-left corner rots last, in minute 6.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == grid.length,n == grid[i].length1 ≤ m, n ≤ 300grid[i][j]is 0, 1 or 2.
Clarifying questions
What you would ask an interviewer before writing any code.