A fruit seller keeps her mangoes in a flat tray, one mango in each cell. The tray is the grid grid, and each cell holds one of these values:
0: nothing is in this cell.1: a fresh fruit.2: a rotten fruit.
Rot spreads in steps. At the end of every minute, each fresh fruit that shares a side with a rotten fruit also becomes rotten. Cells that touch only at a corner do not pass on the rot.
Find how many minutes pass before no fresh fruit is left. If some fresh fruit can never be reached by the rot, return -1. If there is no fresh fruit at the start, the answer is 0.
Examples
Example 1:
Input: grid = [[2,1,0,1],[1,1,0,1],[0,1,1,1]]
Output: 7
Explanation: The rot starts at the top left corner. It walks around the empty column and reaches the last fruit, in the top right corner, at minute 7.
Example 2:
Input: grid = [[2,0,1]]
Output: -1
Explanation: An empty cell sits between the rotten fruit and the fresh one, so the rot can never cross.
Example 3:
Input: grid = [[0,0],[0,2]]
Output: 0
Explanation: There is no fresh fruit to begin with, so no time is needed.