Each blob of connected land is one island. DFS dives into a land cell, floods the entire connected region, then surfaces. Count how many times you had to start a fresh dive.
Scan the grid. When you hit an unvisited 1, that's a new island, so bump the count and DFS-flood every connected land cell, sinking them so you never recount.
DFS goes deep first: it fully explores one branch (recursion / explicit stack) before backtracking.
1 = land, 0 = water+1 island0 doubles as the visited markervoid dfs(vector<vector<char>>& grid, int r, int c) {
int rows = grid.size(), cols = grid[0].size();
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
if (grid[r][c] != '1') return; // water or already sunk
grid[r][c] = '0'; // sink = mark visited
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int r = 0; r < grid.size(); r++)
for (int c = 0; c < grid[0].size(); c++)
if (grid[r][c] == '1') {
count++; // new island found
dfs(grid, r, c); // flood the whole thing
}
return count;
}Each cell is examined a constant number of times across the scan and floods.
Recursion stack in the worst case (grid is entirely land, one giant snake).
Count equals the number of times the outer scan kicks off a fresh DFS.
'0' in place saves a separate visited array. If you can't mutate input, keep a visited[][].