Step 3 of 6
Depth-first flood fill
Depth-first search follows one path as far as it can before backtracking, like exploring a maze by always taking the next unexplored corridor. It's the natural tool for "which things are connected?": pick an unvisited vertex, DFS from it to mark its whole connected component, and count how many times you had to start.
Recursive DFS is elegant, but each call uses stack space, and a big component can overflow the call stack (a thread's stack is typically only 1 to 8 MB, and on this site it's smaller still). Production code often uses an explicit stack: a std::vector on the heap that holds the vertices still to explore.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
int main() {
std::vector<std::string> img = {
"~~~~~~~~",
"~..~~~~~",
"~..~~.~~",
"~~~~~..~",
"~.~~~~~~",
};
int rows = (int)img.size(), cols = (int)img[0].size();
int regions = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (img[r][c] != '.') continue;
regions++;
char mark = char('A' + regions - 1);
std::vector<std::pair<int, int>> stack = {{r, c}};
img[r][c] = mark; // mark when pushing
while (!stack.empty()) {
auto [cr, cc] = stack.back();
stack.pop_back();
const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = cr + dr[d], nc = cc + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || img[nr][nc] != '.') continue;
img[nr][nc] = mark;
stack.push_back({nr, nc});
}
}
}
}
for (const auto& row : img) std::cout << row << "\n";
std::cout << regions << " regions\n";
}
~~~~~~~~
~AA~~~~~
~AA~~B~~
~~~~~BB~
~C~~~~~~
3 regions
How it works
- The outer loops find a cell that isn't part of any region yet. Each time one is found, a new region starts.
- The stack flood-fills from there: pop a cell, look at its four neighbors, and push every one that's still unvisited.
- Cells are marked when pushed, not when popped. Otherwise the same cell could be pushed many times by different neighbors before it's processed, wasting time and memory.
- Changing the grid itself serves as the "visited" record, which is why your task takes the grid by value: it can be modified freely without touching the caller's copy.
This is the "paint bucket" tool in image editors, and the same idea counts islands, rooms in a floor plan, or connected machines in a network.
Your task
Write int count_islands(std::vector<std::string> grid), counting groups of # cells connected up/down/left/right. Use an explicit stack: the test has an island of 250,000 cells.
Challenge 2
Write int largest_island(std::vector<std::string> grid), the number of cells in the biggest group of # cells connected up, down, left or right (0 if there are none). Use an explicit stack or queue, not recursion: one island in the test has 250,000 cells.
Challenge 3
A lake is open water (.) that can't reach the edge of the map. Write int enclosed_cells(const std::vector<std::string>& grid): flood fill from every . on the border, then count the . cells that were never reached. Moves go up, down, left and right; # is land.