How long until every orange has gone bad

A crate of oranges is given as a grid. Each cell is:

• 0 an empty cell,
• 1 a fresh orange,
• 2 a rotten orange.

Every minute, a rotten orange turns every fresh orange directly beside it rotten, up, down, left or right. Report how many minutes until no fresh orange is left. If one can never be reached, report -1.

Worked example#

minute 0      minute 1      minute 2      minute 3      minute 4
2 1 1         2 2 1         2 2 2         2 2 2         2 2 2
1 1 0         2 1 0         2 2 0         2 2 0         2 2 0
0 1 1         0 1 1         0 1 1         0 2 1         0 2 2

So the answer is 4.

Why this is a graph problem#

Every cell is a node and every shared edge is a connection. "How many minutes" is "how many steps away is the furthest orange", and shortest distance in an unweighted graph means breadth-first search.

The one twist is that rot starts in several places at once. That is fine, and the trick is worth knowing on its own: put every rotten orange in the queue before you start. Breadth first then expands all of them together, one ring at a time, and each fresh orange is reached first by whichever source is nearest. It is called a multi-source search, and it costs exactly one extra loop at the start.

Doing it the other way, one search per rotten orange keeping the smallest distance, gives the same answer and takes as many searches as there are sources.

Why depth first will not do#

Depth first reaches every reachable cell too, so it answers "can they all rot". It does not answer "how long", because the first route it happens to take is not the shortest. Whenever a question says shortest, fewest or minimum steps on an unweighted graph, it is breadth first.

Getting the count right#

Count the fresh oranges at the start and decrement as each one turns. At the end, anything left is unreachable, which is the -1 case. That is simpler and harder to get wrong than re-scanning the grid.

Constraints#

• 1 <= rows, columns <= 300