As Far from Land as Possible
Real-world version: The Most Sheltered BerthThe statement here is our own: the same inputs, outputs and technique.
A square chart chart marks each cell 1 for land or 0 for water. A step goes between cells sharing an edge, over land or water alike, and the distance between two cells is the fewest steps between them.
Return the largest distance any water cell sits from its nearest land cell. When the chart is all land or all water, return -1.
Examples
Example 1
- Input
- chart = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
- Output
- 2
The single land cell sits in the middle. Each corner is two steps from it, one across and one down, and nothing on the chart is farther.
Example 2
- Input
- chart = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
- Output
- -1
There is no water anywhere, so there is no berth to measure.
Example 3
- Input
- chart = [[0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
- Output
- 6
The only land sits in the top-right corner, so the bottom-left corner is the farthest berth, three steps down and three across.
Constraints
- 1 <= chart.length <= 100
- Every row of chart is as long as the chart is tall.
- 0 <= chart[i][j] <= 1
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def max_distance(chart: list[list[int]]) -> int:public int maxDistance(int[][] chart)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's