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
C# 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
public int CountRegions(List<List<int>> coverage) {
}Worked examples
| Call | Result |
|---|---|
CountRegions(new List<List<int>> { new List<int> { 1, 1, 0 }, new List<int> { 0, 1, 0 }, new List<int> { 0, 0, 1 } }) | 2 |
CountRegions(new List<List<int>> { new List<int> { 1, 0, 1 }, new List<int> { 0, 0, 0 }, new List<int> { 1, 0, 1 } }) | 4 |
CountRegions(new List<List<int>> { new List<int> { 0, 0 }, new List<int> { 0, 0 } }) | 0 |
CountRegions(new List<List<int>> { new List<int> { 1, 1 }, new List<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 C#
public int CountRegions(List<List<int>> coverage) {
if (coverage.Count == 0) return 0;
int rows = coverage.Count, cols = coverage[0].Count;
var seen = new bool[rows, cols];
int areas = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (coverage[r][c] != 1 || seen[r, c]) continue;
areas++;
var queue = new Stack<(int, int)>();
queue.Push((r, c));
while (queue.Count > 0) {
var (ar, ac) = queue.Pop();
if (ar < 0 || ar >= rows || ac < 0 || ac >= cols) continue;
if (seen[ar, ac] || coverage[ar][ac] != 1) continue;
seen[ar, ac] = true;
queue.Push((ar + 1, ac));
queue.Push((ar - 1, ac));
queue.Push((ar, ac + 1));
queue.Push((ar, ac - 1));
}
}
}
return areas;
}