A classic. The grid holds 1s (land) and 0s (water). An island is a group of 1s connected 4-directionally. Count them.
Write count_islands(grid) that returns the number of distinct islands.
Scan every cell. When you find a 1 you have not visited yet, that is a new island. Increment the count, then flood the whole island (DFS or BFS with neighbors) marking each land cell visited so it is not counted again. A visited set of coordinates keeps you from double-counting.
def neighbors(grid, r, c):
"""Return in-bounds 4-directional neighbor coords: up, down, left, right."""
rows = len(grid)
cols = len(grid[0]) if rows else 0
result = []
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols:
result.append((nr, nc))
return result
def count_islands(grid):
"""Count connected groups of 1s using DFS over the grid."""
# TODO: scan cells; each unvisited 1 starts a new island you then flood
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
A classic. The grid holds 1s (land) and 0s (water). An island is a group of 1s connected 4-directionally. Count them.
Write count_islands(grid) that returns the number of distinct islands.
Scan every cell. When you find a 1 you have not visited yet, that is a new island. Increment the count, then flood the whole island (DFS or BFS with neighbors) marking each land cell visited so it is not counted again. A visited set of coordinates keeps you from double-counting.
Press Run Tests or ⌘↩ to check your solution.