esc to dismiss

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

解体思路

本题在一些算法介绍中给出的思路是 并查集 ,但实际理解题目后我发现用 DFS 更简单。

LeetCode 官方给出三种解法:

  • 深度优先搜索
  • 广度优先搜索
  • 并查集
const LAND byte = '1'
const WATER byte = '0'
const SEARCHED byte = '2'

func dfs(grid [][]byte, i, j int) {
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return
    }

    if grid[i][j] == LAND {
        grid[i][j] = SEARCHED
    } else {
        return
    }

    dfs(grid, i-1, j)
    dfs(grid, i, j-1)
    dfs(grid, i, j+1)
    dfs(grid, i+1, j)
}

func numIslands(grid [][]byte) int {
    num := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == LAND {
                dfs(grid, i, j)
                num++
            } else {
                continue
            }
        }
    }
    return num
}

经验教训

开始实现时我把 DFS 探索的几个索引给搞错了。

dfs(grid, i-1, j)
dfs(grid, i, j-1)
dfs(grid, i, j+1)
dfs(grid, i+1, j)

另外,要注意地图索引不要超出边界值。

if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
    return
}
x