200. Number of Islands

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

1. BFS 广度优先搜索

注意: 若不能直接修改数据, 需要辅助矩阵.

广度优先搜索使用队列进行搜索.

TC: $O(mn)$ SC: $O(min(m,n))$ , 队列最大为$min(m,n)$

func numIslands(grid [][]byte) int {
    count := 0

    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' {
                bfs(grid, r, c)
                count++
            }
        }
    }
    return count
}

func bfs(grid [][]byte, r, c int) {
    // Queue
    q := [][]int{{r,c}}
    // 标记已访问
    grid[r][c] = '0'

    // 移动方向, 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]

        // 邻接节点入队
        for _, dir := range dirs {
            i := cur[0] + dir[0]
            j := cur[1] + dir[1]
            
            isValid := i >=0 && i < len(grid) && j >=0 && j < len(grid[0])
            // 合法坐标 && 未访问
            if isValid && grid[i][j] == '1' {
                q = append(q, []int{i, j})
                // 标记已访问
                grid[i][j] = '0'
            }
        }
    }
}

若不能修改数据, 使用辅助矩阵.

func numIslands(grid [][]byte) int {
    count := 0

    // 访问矩阵
    visited := make([][]bool, len(grid))
    for i := range visited {
        visited[i] = make([]bool, len(grid[0]))
    }

    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' && !visited[r][c] {
                bfs(grid, visited, r, c)
                count++
            }
        }
    }
    return count
}

func bfs(grid [][]byte, visited [][]bool, r, c int) {
    // Queue
    q := [][]int{{r,c}}
    // 标记已访问
    visited[r][c] = true

    // 移动方向, 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]

        // 邻接节点入队
        for _, dir := range dirs {
            i := cur[0] + dir[0]
            j := cur[1] + dir[1]
            
            isValid := i >=0 && i < len(grid) && j >=0 && j < len(grid[0])
            // 合法坐标 && 未访问
            if isValid && grid[i][j] == '1' && !visited[i][j] {
                q = append(q, []int{i, j})
                // 标记已访问
                visited[i][j] = true
            }
        }
    }
}

2. DFS 深度优先搜索

2.1 迭代

使用栈实现深度优先搜索.

func numIslands(grid [][]byte) int {
    count := 0
    
    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' {
                dfs(grid, r, c)
                count++
            }
        }
    }
    return count
}

func dfs(grid [][]byte, r, c int) {
    // Stack
    st := [][]int{{r, c}}
    // 标记访问
    grid[r][c] = '0'

    // 移动方向 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for len(st) > 0 {
        cur := st[len(st)-1]
        st = st[:len(st)-1]
        
        for _, dir := range dirs {
            i := cur[0] + dir[0]
            j := cur[1] + dir[1]
            isValid := i >=0 && i < len(grid) && j >= 0 && j < len(grid[0])

            // 坐标合法 && 未访问
            if isValid && grid[i][j] == '1' {
                st = append(st, []int{i, j})
                // 标记访问
                grid[i][j] = '0'
            }
        }
    }
}

不能修改数据则使用辅助矩阵

func numIslands(grid [][]byte) int {
    count := 0
    
    // 访问矩阵
    visited := make([][]bool, len(grid))
    for i := range visited {
        visited[i] = make([]bool, len(grid[0]))
    }

    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' && !visited[r][c] {
                dfs(grid, visited, r, c)
                count++
            }
        }
    }
    return count
}

func dfs(grid [][]byte, visited [][]bool, r, c int) {
    // Stack
    st := [][]int{{r, c}}
    // 标记访问
    visited[r][c] = true

    // 移动方向 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for len(st) > 0 {
        cur := st[len(st)-1]
        st = st[:len(st)-1]
        
        for _, dir := range dirs {
            i := cur[0] + dir[0]
            j := cur[1] + dir[1]
            isValid := i >=0 && i < len(grid) && j >= 0 && j < len(grid[0])

            // 坐标合法 && 未访问
            if isValid && grid[i][j] == '1' && !visited[i][j] {
                st = append(st, []int{i, j})
                // 标记访问
                visited[i][j] = true
            }
        }
    }
}

2.2 递归

func numIslands(grid [][]byte) int {
    count := 0
    
    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' {
                dfs(grid, r, c)
                count++
            }
        }
    }
    return count
}

func dfs(grid [][]byte, r, c int) {
    if grid[r][c] != '1' {
        return 
    }

    // 标记访问
    grid[r][c] = '0'
    // 移动方向 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range dirs {
        i := r + dir[0]
        j := c + dir[1]
        isValid := i >=0 && i < len(grid) && j >= 0 && j < len(grid[0])
        // 坐标合法
        if isValid {
            dfs(grid, i, j)
        }
    }
}

不能修改数据, 则使用辅助矩阵

func numIslands(grid [][]byte) int {
    count := 0
    
    // 访问矩阵
    visited := make([][]bool, len(grid))
    for i := range visited {
        visited[i] = make([]bool, len(grid[0]))
    }

    for r := range grid {
        for c := range grid[r] {
            // 未访问
            if grid[r][c] == '1' && !visited[r][c] {
                dfs(grid, visited, r, c)
                count++
            }
        }
    }
    return count
}

func dfs(grid [][]byte, visited [][]bool, r, c int) {
    // 不为'1' 或 已访问
    if grid[r][c] != '1' || visited[r][c] {
        return 
    }

    visited[r][c] = true
    // 移动方向 上下左右
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range dirs {
        i := r + dir[0]
        j := c + dir[1]
        isValid := i >=0 && i < len(grid) && j >= 0 && j < len(grid[0])

        // 坐标合法
        if isValid {
            dfs(grid, visited, i, j)
        }
    }
}

3. 并查集

将$m\times n$的矩阵, 每个位置赋值i*n + j, 可以使得将矩阵每行合并成一维数组时, 数组下标和值刚好相等.

例如: $3\times3$的矩阵:

[0 0 0]		 [0 1 2]
[0 0 0] -->  [3 4 5]
[0 0 0]		 [6 7 8]

此时可以做坐标之间的映射了.

1. 初始化并查集, 扫描矩阵, 统计节点数量
2. 扫描矩阵, 对于每个岛屿, 以其为起点
3. 将相邻岛屿合并, 直到不能再合并为止.

此时剩下的岛屿数量就是当前的岛屿数量.

func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    // 并查集
    parents := make([]int, m*n)
    // 初始化
    count := 0
    for r := range grid {
        for c := range grid[r] {
            if grid[r][c] == '1' {
                parents[r*n+c] = r*n + c
                count++
            }
        }
    }

    return uniteIsland(grid, parents, count)
}

func uniteIsland(grid [][]byte, parents []int, count int) int {
    for r := range grid {
        for c := range grid[r] {
            if grid[r][c] == '1' {
                // 移动方向 上下左右
                dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

                for _, dir := range dirs{
                    i := r + dir[0]
                    j := c + dir[1]
                    isValid := i >=0 && i < len(grid) && j >= 0 && j < len(grid[0])
                    n := len(grid[0])
                    if isValid && grid[i][j] == '1' && union(parents, r*n+c, i*n+j) {
                        count--
                    }
                }
            }
        }
    }
    return count
}

func findParent(parents []int, i int) int {
    if parents[i] != i {
        parents[i] = findParent(parents, parents[i])
    }
    return parents[i]
}

func union(parents []int, i, j int) bool {
    pi := findParent(parents, i)
    pj := findParent(parents, j)

    if pi != pj {
        parents[pi] = pj
        return true
    }
    return false
}

Reference

1. https://leetcode.cn/problems/number-of-islands/solutions/