Practice: Counting Islands
Graphs in a grid.
Here's a map, made of ones for land and zeros for water. How many islands are there? An island is land connected up, down, left, or right. Pause. Where's the graph?

- A map of 1s and 0s
- How many islands?
- Where's the graph?
Sinking each island
Each land cell is a node, connected to its land neighbours. We scan the grid. When we find unvisited land, that's a new island, so we count it, and flood fill it with depth first search, marking every connected land cell as seen. Run it. Three islands.
from grid import grid
def count_islands(grid):
rows, cols, seen = len(grid), len(grid[0]), set()
def sink(r, c):
if not (0 <= r < rows and 0 <= c < cols): return
if grid[r][c] == "0" or (r, c) in seen: return
seen.add((r, c))
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
sink(r + dr, c + dc)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
islands += 1
sink(r, c)
return islands
print(count_islands(grid))3
Also uses grid.py
grid = [
"11000",
"11010",
"00011",
"10000",
]Grids are graphs
Many puzzles hide a graph inside a grid. Mazes, flood fill in paint programs, and game maps. Each cell is a node, and its neighbours are the cells around it. Once you see the graph, breadth first and depth first search solve them all. This takes O of rows times columns.
| key | value |
|---|---|
| Cell | a node |
| Neighbours | up, down, left, right |
| Flood fill | DFS or BFS |
| Cost | O(rows × cols) |
Summary
Treat each land cell as a node, and flood fill each new island with depth first search. Next, graphs where edges have weights.
Key takeaways- Scan for land
- New land? Count it
- Flood fill to mark it