Number of Islands

1. Problem Description

Given a 2D grid consisting of '1' (land) and '0' (water), calculate the number of islands in the grid.

An island is always surrounded by water, and each island is formed only by horizontally and/or vertically adjacent land cells.

You may also assume that all four edges of the grid are surrounded by water.

2. Approach

1. Approach 1
   • DFS
   • Whenever a '1' is encountered, enumerate all reachable coordinates in the four directions
   • Use a set to record visited (i,j) positions

3. Implementation

3.1. DFS

func numIslands(grid [][]byte) int {
    maxRow := len(grid)
    maxCol := len(grid[0])
    visited := make([][]bool, maxRow)
    for i:=0; i < len(visited);i++{
        visited[i] = make([]bool, maxCol)
    }

    count := 0
    for i := range grid {
        for j := range grid[i] {
            if !visited[i][j] && grid[i][j] == '1' {
                visitIsland(grid, i, j, maxRow, maxCol, visited)
                count++
            }
        }
    }
    return count
}

func visitIsland(grid [][]byte, row, col, maxRow, maxCol int, visited [][]bool) {
    if row < 0 || row >= maxRow || col < 0 || col >= maxCol {
        return
    }

    if grid[row][col] == '0' {
        return 
    }

    if visited[row][col] {
        return
    }

    visited[row][col] = true
    visitIsland(grid, row+1, col, maxRow, maxCol, visited)
    visitIsland(grid, row-1, col, maxRow, maxCol, visited)
    visitIsland(grid, row, col+1, maxRow, maxCol, visited)
    visitIsland(grid, row, col-1, maxRow, maxCol, visited)
}

4. References

• 200. Number of Islands - LeetCode