C++ Program To Count Number Of Islands Where Every Island Is Row Wise And Column Wise Separated

Counting islands in a 2D grid is a fundamental problem in computer science, often used to introduce graph traversal algorithms. This problem involves identifying distinct groups of connected land cells within a matrix representing a map.

In this article, you will learn how to effectively count the number of islands in a 2D binary grid using a depth-first search (DFS) approach in C++, where islands are defined by horizontally and vertically connected land cells.

Problem Statement

The challenge is to determine the total number of distinct islands present in a given 2D grid. The grid consists of '1's (representing land) and '0's (representing water). An island is formed by a group of connected '1's, where connection implies adjacency horizontally or vertically. Critically, land cells belonging to the same island are always row-wise and column-wise separated, meaning diagonal connections do not form an island.

Consider a scenario where you have a map represented as a matrix of land and water. Identifying distinct landmasses (islands) helps in various spatial analyses, from geographical mapping to image processing.

Example

Let's consider the following grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

In this grid, the expected number of islands is 3.

• The first island is at the top-left (the 2x2 block of '1's).
• The second island is the isolated '1' in the middle.
• The third island is the 1x2 block of '1's at the bottom-right.

Background & Knowledge Prerequisites

To understand and implement the solution for counting islands, you should have a basic understanding of:

• C++ fundamentals: Variables, loops, functions, and conditional statements.
• 2D arrays or vectors: How to declare, initialize, and access elements in a two-dimensional structure.
• Recursion: The concept of a function calling itself.
• Depth-First Search (DFS): A graph traversal algorithm that explores as far as possible along each branch before backtracking. While this problem isn't explicitly a graph, the grid cells and their connections can be modeled as such.

Use Cases or Case Studies

The "count islands" problem, or its underlying concept of finding connected components, applies to several real-world scenarios:

• Image Processing: Identifying distinct objects or regions in a binary image (e.g., distinguishing individual cells in a microscopy image).
• Game Development: Analyzing game maps to determine traversable landmasses, distinct territories, or enclosed areas.
• Network Analysis: Finding disconnected sub-networks or clusters in a larger system, where '1' might represent a connection and '0' an absence.
• Geographical Information Systems (GIS): Counting actual islands or isolated landmasses from satellite imagery data.
• Maze Solving: Similar algorithms are used to find paths or identify distinct rooms in a maze.

Solution Approaches

A highly effective approach for counting islands is to use a traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS). We will focus on the DFS method due to its elegant recursive implementation for this problem.

Count Islands using Depth-First Search (DFS)

This approach systematically explores each land cell and marks all connected land cells as visited, ensuring that each island is counted exactly once.

One-line summary: Iterate through the grid, and whenever a land cell ('1') is found, increment the island count and then perform a DFS to mark all its connected land cells as visited (e.g., change them to '0').

Code example:

// 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;
}

Run

Sample output:

Number of islands in grid 1: 3
Number of islands in grid 2: 1
Number of islands in grid 3: 5

Stepwise explanation for clarity:

1. numIslands function: This is the main function that orchestrates the counting process.

• It first handles the edge case of an empty grid.
• It initializes island_count to zero.
• It then iterates through every cell (r, c) in the grid.

1. Finding an unvisited land cell: If grid[r][c] is '1', it signifies that a part of an island has been found that has not yet been explored.

• island_count is incremented.
• The dfs function is called to explore and mark all connected land cells belonging to this newly found island.

1. dfs function: This recursive helper function performs the depth-first traversal.

• Base Cases: It checks if the current cell (r, c) is out of bounds or if it's water ('0'). If any of these conditions are true, the recursion stops for that path.
• Marking as Visited: If the cell is a valid land cell ('1'), it's immediately marked as '0'. This step is crucial because it prevents the algorithm from:
• Recounting parts of the same island.
• Entering an infinite loop for connected cells.
• Recursive Calls: The dfs function then recursively calls itself for all four adjacent neighbors (up, down, left, right). This process continues until all connected land cells of the current island have been visited and marked as '0'.

1. Iteration Continuation: After the dfs call returns, the numIslands function continues its iteration. Any '1' encountered later will belong to a *different* island because all cells of previously found islands would have been changed to '0'.
2. Return Value: Finally, numIslands returns the total island_count.

Conclusion

Counting islands in a 2D grid is a classic problem demonstrating the power of graph traversal algorithms like Depth-First Search. By systematically exploring connected components and marking visited cells, we efficiently determine the number of distinct landmasses. This method is robust, handles various grid configurations, and serves as a fundamental building block for solving more complex grid-based problems.

Summary

• The problem involves counting groups of horizontally/vertically connected '1's (land) in a grid of '0's (water).
• Depth-First Search (DFS) is an effective algorithm to solve this problem.
• The DFS algorithm starts at an unvisited land cell, increments the island count, and then recursively visits all adjacent land cells, marking them as visited (e.g., changing '1' to '0').
• Marking cells as visited prevents recounting islands and infinite loops.
• This approach is widely applicable in areas like image processing, game development, and network analysis.