hardGraphsPure DSA~30 min
Most Remote Cell From Any Covered Region
On a grid, some cells host coverage (value 1) and the rest are gaps (value 0). Find the gap cell whose Manhattan distance to the nearest coverage cell is the largest; report that distance.
Problem
Given an n x n grid of 0s (water) and 1s (land), find a water cell whose distance to the nearest land cell is maximized, and return that distance using Manhattan distance. If no land or no water exists, return -1.
Input
An n x n integer grid of 0s and 1s.
Output
An integer: the maximum nearest-land distance, or -1.
Constraints
- 1 <= n <= 100
- grid[i][j] is 0 or 1.
- Distance is |r1 - r2| + |c1 - c2|.
Examples
Example 1
Input
grid = [[1,0,1],[0,0,0],[1,0,1]]
Output
2
The center cell is distance 2 from the nearest land.
Example 2
Input
grid = [[1,0,0],[0,0,0],[0,0,0]]
Output
4
The far corner is 4 steps from the single land cell.