377. How Long Until Everything Rots
A crate of fruit is given as a grid. 0 is an empty cell, 1 is a fresh
fruit, and 2 is a rotten one.
Each minute, every rotten fruit rots any fresh fruit directly above, below, left or right of it. Print how many minutes pass until no fresh fruit is left.
Print -1 if some fresh fruit can never rot.
The new idea here is that the search starts from MANY places at once. Put every rotten cell into the queue before the first step, all at distance 0. Running a separate search per rotten cell and adding the results would be wrong, because the rot spreads in parallel and a fruit rots at the earliest time any source reaches it.
The answer is the largest distance the search hands out. If the grid begins with no fresh fruit at all, nothing has to happen and the answer is 0.
Constraints - `1 ≤ r ≤ 1000` - `1 ≤ c ≤ 1000` - Every value is `0`, `1` or `2`.
Input
The first line contains two integers r and c, the number of rows and
columns. Each of the next r lines contains c integers separated by spaces,
each 0, 1 or 2.
Output
Print one integer, the number of minutes, or -1 if some fruit never rots.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.