101
0/320
Loading content...
You are given a square map represented as an n × n grid containing two types of terrain: ocean cells marked as 0 and island cells marked as 1.
Your task is to find an ocean cell that is positioned as far as possible from any island cell, and return that maximum distance. The distance metric used is the Manhattan distance, which between two cells at positions (r₁, c₁) and (r₂, c₂) is calculated as |r₁ - r₂| + |c₁ - c₂|.
If the grid contains only ocean cells (no islands) or only island cells (no ocean), return -1 since no valid ocean-to-island distance can be computed.
Key Insight: You need to identify which ocean cell has the greatest minimum distance to its nearest island. This means for each ocean cell, calculate the distance to the closest island, then return the maximum among all these minimum distances.
grid = [[1,0,1],[0,0,0],[1,0,1]]2The center cell at position (1, 1) is an ocean cell. Its nearest islands are at corners: (0,0), (0,2), (2,0), and (2,2), each at Manhattan distance 2. No other ocean cell is farther from all islands, so the answer is 2.
grid = [[1,0,0],[0,0,0],[0,0,0]]4The only island is at position (0, 0). The ocean cell farthest from this island is at (2, 2), with Manhattan distance |2-0| + |2-0| = 4.
grid = [[0,0,0],[0,1,0],[0,0,0]]2The island is at the center (1, 1). The farthest ocean cells are at the four corners (0,0), (0,2), (2,0), and (2,2), each at Manhattan distance 2 from the central island.
Constraints