Grid DFS (Island Counting)

Concept

Grid DFS recursively explores connected cells in a 2D grid. When we find an unvisited land cell, we start a DFS that marks all connected land cells as visited (by modifying the grid). Each DFS call covers one connected component — one 'island'.

When to Use

  • ▸Counting connected components (islands) in a grid
  • ▸Flood fill / painting connected regions
  • ▸Finding the area of the largest connected region
  • ▸Any grid problem where you need to explore all cells connected to a starting cell

Intuition

Imagine a grid of land ('1') and water ('0'). To count islands, scan every cell. When you find land, that's a new island — then 'sink' the entire island by marking all connected land as water via DFS. Next time you find land, it must be a different island. The number of times you trigger DFS = number of islands.

Complexity

Time
O(M * N)
Space
O(M * N) recursion stack worst case

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

void f(int i, int j, vector<vector<char>>& grid){
    int n = grid.size(), m = grid[0].size();

    if(i < 0 || j < 0 || i >= n || j >= m) return;
    if(grid[i][j] == '0') return;

    grid[i][j] = '0';

    f(i-1, j, grid);
    f(i+1, j, grid);
    f(i, j-1, grid);
    f(i, j+1, grid);
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<char>> grid(n, vector<char>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == '1'){
                cnt++;
                f(i, j, grid);
            }
        }
    }

    cout << cnt << "\n";

    return 0;
}

// Sample Input:
// 4 5
// 1 1 0 0 0
// 1 1 0 0 0
// 0 0 1 0 0
// 0 0 0 1 1
//
// Sample Output:
// 3