All problems

As Far from Land as Possible

Medium · graph traversal

You are given a map as a rectangular grid of integers, grid. A cell holding 1 is land and a cell holding 0 is water.

The distance between two cells is the number of steps needed to walk from one to the other when each step moves up, down, left or right by one cell. You may walk across land and water alike, so the distance between the cells in rows r1, r2 and columns c1, c2 is |r1 - r2| + |c1 - c2|.

Pick the water cell whose nearest land cell is as far away as possible, and return that distance. If the grid has no land, or has no water, return -1.

Examples

Example 1

Input: grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Output: 2

The middle cell is 2 steps from each of the four corners, which is the farthest any water cell gets from land.

Example 2

Input: grid = [[1, 0, 0], [0, 0, 0], [0, 0, 0]]

Output: 4

The bottom-right cell is 2 rows and 2 columns away from the only land cell.

Example 3

Input: grid = [[1, 1], [1, 1]]

Output: -1

There is no water cell.

Constraints

• 1 <= rows, cols <= 30
• Every cell is either 0 (water) or 1 (land).
• All rows have the same length.