Number of Islands - Java Solution

1. Introduction

This blog post delves into the "Number of Islands" problem, a common question in graph theory and depth-first search algorithms. The problem involves identifying distinct islands in a grid, where an island is defined as a group of adjacent lands ('1's) surrounded by water ('0's). It is a frequent challenge in areas like geographic information systems and game development.

Problem

Given an m x n 2D binary grid grid representing 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 is formed by connecting adjacent lands horizontally or vertically.

2. Solution Steps

1. Traverse the grid cell by cell.

2. When a land cell ('1') is found, increment the island count and perform a depth-first search (DFS) from that cell to mark all adjacent land cells as visited.

3. In the DFS process, mark the current land cell as visited (e.g., set to '0') and recursively call DFS for its adjacent unvisited land cells.

4. Continue the process until all cells in the grid have been visited.

5. Return the total count of islands found.

3. Code Program

public class NumberOfIslands {
    public static void main(String[] args) {
        char[][] grid = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println(numIslands(grid)); // Test the function
    }

    // Function to count the number of islands
    public static int numIslands(char[][] grid) {
        int numIslands = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(grid, i, j);
                }
            }
        }

        return numIslands;
    }

    // Helper function for depth-first search
    private static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

Output:

3

Explanation:

1. numIslands: This function iterates through each cell in the grid. Whenever it finds a land cell ('1'), it increases the island count and calls the dfs function to mark the entire island.

2. dfs: This recursive function marks the visited land cells by changing them to '0'. It explores all adjacent cells (up, down, left, right) that are part of the current island.

3. The dfs function uses boundary checks to prevent out-of-bounds access and ensures that only land cells are visited.

4. Each call to dfs marks an entire island, and the main function continues to count and mark other islands.

5. The total number of recursive dfs calls gives the count of islands in the grid.

6. This approach effectively uses depth-first search to explore and mark cells of each island, ensuring all connected lands are counted as one island.