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
Java 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
int countRegions(List<List<Integer>> coverage) {
}Worked examples
| Call | Result |
|---|---|
countRegions(Main.<List<Integer>>ls(Main.<Integer>ls(1, 1, 0), Main.<Integer>ls(0, 1, 0), Main.<Integer>ls(0, 0, 1))) | 2 |
countRegions(Main.<List<Integer>>ls(Main.<Integer>ls(1, 0, 1), Main.<Integer>ls(0, 0, 0), Main.<Integer>ls(1, 0, 1))) | 4 |
countRegions(Main.<List<Integer>>ls(Main.<Integer>ls(0, 0), Main.<Integer>ls(0, 0))) | 0 |
countRegions(Main.<List<Integer>>ls(Main.<Integer>ls(1, 1), Main.<Integer>ls(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 Java
int countRegions(List<List<Integer>> coverage) {
if (coverage.isEmpty()) return 0;
int rows = coverage.size(), cols = coverage.get(0).size();
boolean[][] seen = new boolean[rows][cols];
int areas = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (coverage.get(r).get(c) != 1 || seen[r][c]) continue;
areas++;
Deque<int[]> queue = new ArrayDeque<>();
queue.push(new int[] { r, c });
while (!queue.isEmpty()) {
int[] at = queue.pop();
int ar = at[0], ac = at[1];
if (ar < 0 || ar >= rows || ac < 0 || ac >= cols) continue;
if (seen[ar][ac] || coverage.get(ar).get(ac) != 1) continue;
seen[ar][ac] = true;
queue.push(new int[] { ar + 1, ac });
queue.push(new int[] { ar - 1, ac });
queue.push(new int[] { ar, ac + 1 });
queue.push(new int[] { ar, ac - 1 });
}
}
}
return areas;
}