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 turn: 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.