How many separate areas on the map
A coverage map marks every square metre as served or not. Planning wants the number of separate served areas, so a served square touching another one edge to edge belongs to the same area.
- A cell holding 1 is served; 0 is not.
- Two served cells belong to the same area when they touch above, below, left or right — not diagonally.
- Return how many separate served areas there are.
- An empty map has no areas.
count_regions(coverage: list<list<int>>) → int
Where you start
def count_regions(coverage: list[list[int]]) -> int:
Worked examples
| Call | Result |
|---|---|
count_regions([[1, 1, 0], [0, 1, 0], [0, 0, 1]]) | 2 |
count_regions([[1, 0, 1], [0, 0, 0], [1, 0, 1]]) | 4 |
count_regions([[0, 0], [0, 0]]) | 0 |
count_regions([[1, 1], [1, 1]]) | 1 |
Hint
Walk every cell. The first time you meet an unvisited served cell, that is a new area — then flood outwards from it, marking everything it reaches, so you never count it twice.
Reference solution in Python
def count_regions(coverage: list[list[int]]) -> int:
if not coverage:
return 0
rows, cols = len(coverage), len(coverage[0])
seen = [[False] * cols for _ in range(rows)]
def flood(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if seen[r][c] or coverage[r][c] != 1:
return
seen[r][c] = True
flood(r + 1, c)
flood(r - 1, c)
flood(r, c + 1)
flood(r, c - 1)
areas = 0
for r in range(rows):
for c in range(cols):
if coverage[r][c] == 1 and not seen[r][c]:
areas += 1
flood(r, c)
return areas