Example: Count Number of Islands in C++

// Count Number of Islands
#include <iostream>
#include <vector>
#include <queue> // Not strictly needed for DFS, but good to include for graph algorithms

using namespace std;

// Helper function for DFS traversal
void dfs(vector<vector<char>>& grid, int r, int c) {
    int rows = grid.size();
    int cols = grid[0].size();

    // Base cases:
    // 1. Out of bounds
    // 2. Current cell is water ('0')
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') {
        return;
    }

    // Mark the current cell as visited by changing '1' to '0'
    // This prevents recounting and cycles
    grid[r][c] = '0';

    // Explore neighbors (up, down, left, right)
    dfs(grid, r + 1, c); // Down
    dfs(grid, r - 1, c); // Up
    dfs(grid, r, c + 1); // Right
    dfs(grid, r, c - 1); // Left
}

// Function to count the number of islands
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        return 0; // Handle empty grid case
    }

    int num_rows = grid.size();
    int num_cols = grid[0].size();
    int island_count = 0;

    // Iterate through each cell in the grid
    for (int r = 0; r < num_rows; ++r) {
        for (int c = 0; c < num_cols; ++c) {
            // If a land cell ('1') is found, it's the start of a new island
            if (grid[r][c] == '1') {
                island_count++;
                // Perform DFS to mark all connected land cells as visited
                dfs(grid, r, c);
            }
        }
    }

    return island_count;
}

int main() {
    // Step 1: Define the grid
    vector<vector<char>> grid1 = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    // Step 2: Count islands for grid1
    cout << "Number of islands in grid 1: " << numIslands(grid1) << endl; // Expected: 3

    // Step 3: Define another grid for testing
    vector<vector<char>> grid2 = {
        {'1', '1', '1'},
        {'1', '1', '0'},
        {'1', '0', '1'}
    };

    // Step 4: Count islands for grid2
    cout << "Number of islands in grid 2: " << numIslands(grid2) << endl; // Expected: 1 (all connected)

    vector<vector<char>> grid3 = {
        {'1', '0', '1'},
        {'0', '1', '0'},
        {'1', '0', '1'}
    };

    // Step 5: Count islands for grid3
    cout << "Number of islands in grid 3: " << numIslands(grid3) << endl; // Expected: 5 (isolated '1's)
    
    return 0;
}