Number of Islands - C Solution

1. Introduction

In this post, we explore a common problem in graph algorithms often presented as "Number of Islands". This problem involves analyzing a 2D grid of '1's (land) and '0's (water) to count the number of distinct islands. An island is defined as a group of adjacent lands, connected vertically or horizontally. The challenge lies in efficiently traversing the grid and identifying distinct landmasses.

Problem

Given an m x n 2D binary grid, which represents a map of '1's (land) and '0's (water), the task is to return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically. It is assumed that all four edges of the grid are surrounded by water.

2. Solution Steps

1. Initialize a count for islands to 0.

2. Traverse the grid. For each cell:

a. If the cell value is '1', increment the island count and perform a Depth-First Search (DFS) from that cell.

b. In DFS, mark the current land cell as visited by setting it to '0' and recursively check its adjacent cells (up, down, left, right).

3. Continue the process for all cells in the grid.

4. Return the total count of islands.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

void dfs(char** grid, int gridSize, int* gridColSize, int row, int col) {
    if (row < 0 || col < 0 || row >= gridSize || col >= gridColSize[row] || grid[row][col] == '0') {
        return;
    }

    // Mark the current cell as visited
    grid[row][col] = '0';

    // Check all four adjacent directions
    dfs(grid, gridSize, gridColSize, row + 1, col);
    dfs(grid, gridSize, gridColSize, row - 1, col);
    dfs(grid, gridSize, gridColSize, row, col + 1);
    dfs(grid, gridSize, gridColSize, row, col - 1);
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int islandCount = 0;

    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] == '1') {
                islandCount++;
                dfs(grid, gridSize, gridColSize, i, j);
            }
        }
    }

    return islandCount;
}

// Main function to test the numIslands function
int main() {
    char* grid[] = {
        "11110",
        "11010",
        "11000",
        "00000"
    };
    int gridSize = 4;
    int gridColSize[] = {5, 5, 5, 5};

    int result = numIslands(grid, gridSize, gridColSize);
    printf("Number of Islands: %d\n", result);

    return 0;
}

Output:

Number of Islands: 1

Explanation:

1. numIslands initializes a counter for islands and iterates through the grid.

2. For each land cell ('1'), it increments the island count and calls dfs to mark all connected lands as visited.

3. dfs function recursively visits and marks adjacent lands.

4. The final count of islands is returned after traversing the entire grid.

5. The main function demonstrates the functionality with a sample grid.