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.
countRegions(coverage: list<list<int>>) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func countRegions(coverage [][]int) int {
}Worked examples
| Call | Result |
|---|---|
countRegions([][]int{[]int{1, 1, 0}, []int{0, 1, 0}, []int{0, 0, 1}}) | 2 |
countRegions([][]int{[]int{1, 0, 1}, []int{0, 0, 0}, []int{1, 0, 1}}) | 4 |
countRegions([][]int{[]int{0, 0}, []int{0, 0}}) | 0 |
countRegions([][]int{[]int{1, 1}, []int{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 Go
func countRegions(coverage [][]int) int {
if len(coverage) == 0 {
return 0
}
rows, cols := len(coverage), len(coverage[0])
seen := make([][]bool, rows)
for i := range seen {
seen[i] = make([]bool, cols)
}
var flood func(r, c int)
flood = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols {
return
}
if seen[r][c] || 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 := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if coverage[r][c] == 1 && !seen[r][c] {
areas++
flood(r, c)
}
}
}
return areas
}