Rotting oranges
A crate of oranges is a grid grid with rows rows and cols columns. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Rot spreads one step per minute: when a minute passes, every fresh orange with a rotten orange directly above, below, left or right of it turns rotten too. Rot does not cross corners or empty cells.
How many minutes pass before the crate holds no fresh orange? Return that number. Return 0 if the crate starts with no fresh orange, and -1 if some fresh orange can never rot. You may change grid while you work.
Cells are written (row, column), counting from 0.
grid = [[0, 2, 1, 1], [1, 1, 0, 1], [1, 0, 0, 1]]Output4Minute 1 rots (1, 1) and (0, 2). Minute 2: (1, 0) and (0, 3). Minute 3: (2, 0) and (1, 3). Minute 4: (2, 3), the last fresh orange.
grid = [[2, 0, 1], [1, 0, 1]]Output-1(1, 0) rots in minute 1, but the empty middle column cuts the two oranges on the right off from the rot.
grid = [[2, 0, 2]]Output0There is no fresh orange, so no time needs to pass.
1 ≤ rows, cols ≤ 200
Every cell is 0, 1 or 2.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.