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'

思路#

for 循环检查每个节点，在检查过程中使用一个“传染函数”，递归地将每个接触到的 '1' 改为 '2'（或其他对判别陆地、水无影响的值），以此标记不同的岛屿。

代码#

func numIslands(grid [][]byte) int {
    islandNum := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            // 岛屿数++
            if grid[i][j] == '1' {
                // 先传染再 ++
                infect(grid, i, j)
                islandNum++
            }
        }
    }
    return islandNum
}

func infect(grid [][]byte, i, j int) {
    // 跳出条件
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
        return
    }

    // 递归标记
    grid[i][j] = '2'
    infect(grid, i-1, j)
    infect(grid, i+1, j)
    infect(grid, i, j-1)
    infect(grid, i, j+1)
}