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
int countRegions(std::vector<std::vector<int>> coverage) {
}Worked examples
| Call | Result |
|---|---|
countRegions(std::vector<std::vector<int>>{std::vector<int>{1, 1, 0}, std::vector<int>{0, 1, 0}, std::vector<int>{0, 0, 1}}) | 2 |
countRegions(std::vector<std::vector<int>>{std::vector<int>{1, 0, 1}, std::vector<int>{0, 0, 0}, std::vector<int>{1, 0, 1}}) | 4 |
countRegions(std::vector<std::vector<int>>{std::vector<int>{0, 0}, std::vector<int>{0, 0}}) | 0 |
countRegions(std::vector<std::vector<int>>{std::vector<int>{1, 1}, std::vector<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++
int countRegions(std::vector<std::vector<int>> coverage) {
if (coverage.empty()) return 0;
int rows = static_cast<int>(coverage.size());
int cols = static_cast<int>(coverage[0].size());
std::vector<std::vector<bool>> seen(rows, std::vector<bool>(cols, false));
std::function<void(int, int)> flood = [&](int r, int c) {
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);
};
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]) {
areas++;
flood(r, c);
}
}
}
return areas;
}