Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Intermediate Level

Implement the numberOfIslandsDfsCount method that counts islands in a grid using depth-first search.

The input contains a grid of 1s and 0s. A value of 1 represents land, and a value of 0 represents water.

Your task is to count how many separate islands are present in the grid. An island is formed by connected land cells in the up, down, left, and right directions.

Diagonal cells are not considered connected.

Example 1
Input:
grid (int[][]) = [[1,1,0],[0,1,0],[1,0,1]]
rows (int) = 3
cols (int) = 3
Return:
(int) 3
Example 2
Input:
grid (int[][]) = [[1,1],[1,1]]
rows (int) = 2
cols (int) = 2
Return:
(int) 1
Example 3
Input:
grid (int[][]) = [[1,0],[0,1]]
rows (int) = 2
cols (int) = 2
Return:
(int) 2

Use depth-first search to explore each island completely.

Scan every cell in the grid. When an unvisited land cell is found, it starts a new island, so increase the island count. Then run DFS from that cell to mark all connected land cells as visited.

By marking the whole island as visited, the same island will not be counted again.

Pseudocode:

function numberOfIslandsDfsCount(grid, rows, cols):
    visited = 2D boolean array filled with false
    islands = 0
    for r from 0 to rows - 1:
        for c from 0 to cols - 1:
            if grid[r][c] == 1 and visited[r][c] == false:
                islands++
                dfs(r, c)
    return islands
function dfs(r, c):
    if r is outside grid or c is outside grid:
        return
    if grid[r][c] == 0 or visited[r][c] == true:
        return
    visited[r][c] = true
    dfs(r - 1, c)
    dfs(r + 1, c)
    dfs(r, c - 1)
    dfs(r, c + 1)
Run your code to see the result.