Loading...
Loading...
You are given a 2D grid representing a satellite image. Each cell is either land (1) or water (0). The image may contain multiple islands.
An island is a contiguous region of land cells connected via 8-directional adjacency, including diagonals.
A body of water is a contiguous region of water cells connected via 4-directional adjacency, no diagonals.
A lake is a body of water that does not touch any edge of the grid. Water that reaches the grid boundary is ocean, not a lake.
A lake belongs to an island if every land cell 4-directionally adjacent to the lake is part of that island. If a lake borders more than one island, it belongs to none of them. Note that an island may sit inside a lake of another island, and that inner island may have lakes of its own.
Given the grid and a starting coordinate [row, col] guaranteed to be a land cell on one of the islands, return the number of lakes that belong to that island.
Input:
image = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]
start = [1, 1]
Output: 1
Explanation: One lake enclosed by the island.
Input:
image = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]
start = [1, 1]
Output: 0
Explanation: Solid land block with no enclosed water.
rows, cols ≤1000rows × cols ≤106