Minimum Farthest Cell After Adding One Source

You are given an n x m binary matrix grid. Cells equal to 1 are sources; cells equal to 0 are empty.

The distance between two cells (r1, c1) and (r2, c2) is the Chebyshev distance max(|r1 - r2|, |c1 - c2|). For example, (1, 2) and (0, 4) are at distance max(1, 2) = 2.

The spread of the grid is the largest distance from any empty cell to its nearest source. A grid with no empty cells has spread 0.

You may convert at most one empty cell into a source. Return the minimum spread that can be achieved.

If the grid contains no source at all, the cell you convert becomes the only source.

Examples

Example 1

Input: grid = [[0,0,0,1],[0,0,0,1]]
Output: 1
Explanation: The distances to the nearest source are
  3 2 1 0
  3 2 1 0
so the spread is 3. Converting (0,0) gives
  0 1 1 0
  1 1 1 0
and every empty cell is now within distance 1.

Example 2

Input: grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0]]
Output: 2
Explanation: There is no source. Converting (1,1) gives distances
  1 1 1 2
  1 0 1 2
  1 1 1 2
with spread 2; no single cell does better.

Example 3

Input: grid = [[1,1],[1,1]]
Output: 0
Explanation: There are no empty cells, so the spread is already 0.