200 岛屿数量

题目描述#

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿被水包围，只能由水平或竖直方向相邻的陆地连接而成，网格四条边均视为水域。

思路#

遍历整个网格，遇到 '1' 就说明找到了一座新的岛屿，答案加一，同时对这个格子发起 DFS，把它所能连通的所有陆地格子都标记为 '2'（“插旗”）。

DFS 的递归逻辑很直接：当前格子出界、或不是 '1'，就直接返回；否则把当前格子改成 '2'，然后向上下左右四个方向继续递归。标记为 '2' 而不是 '0' 是为了和原始水域区分，也可以用任意其他非 '1' 的值。

遍历结束时，所有陆地都已被访问过并标记，ans 就是岛屿总数。

知识边界#

DFS 四方向扩散是网格连通分量问题的基本套路，适用于岛屿类题目
将已访问的 '1' 改为其他值（本题用 '2'）是避免重复访问的常见手法，不需要额外的 visited 数组
递归出口必须在修改格子之前判断，否则越界访问会 panic

代码#

func numIslands(grid [][]byte) (ans int) {
    m, n := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(i, j int) {
        // 出界，或者不是 '1'，就不再往下递归
        if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' {
            return
        }
        grid[i][j] = '2' // 插旗！避免来回横跳无限递归
        dfs(i, j-1)      // 往左走
        dfs(i, j+1)      // 往右走
        dfs(i-1, j)      // 往上走
        dfs(i+1, j)      // 往下走
    }

    for i, row := range grid {
        for j, c := range row {
            if c == '1' { // 找到了一个新的岛
                dfs(i, j) // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                ans++
            }
        }
    }
    return
}