200. 岛屿数量 Medium

给你一个由 '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

解题思路

输入： 一个由 '1'（陆地）和 '0'（水）组成的的二维网格

输出： 计算岛屿数量

本题属于网格图 DFS 类问题。

当我们遍历到 1(陆地) 的时候，我们要先将这个陆地标记为已探索状态（可以标记为 0 或用 visited 数组记录），之后在对这块陆地的上下左右进行深度探索，直到探索到边界或者周围都是 0 为止。

这个过程就是 DFS 遍历.

当我们对网格里面的值都探索过后，所有的陆地都会变为 0 或者 记录在 visited 里。

每当我们第一次遇到 1 时就代表遇到了一个岛屿，我们只需要记录第一次遇到 1(陆地) 的次数即可

代码实现

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])  # 获取行数和列数

        # 定义一个 DFS 函数，用于“淹掉”当前岛屿
        def dfs(r, c):
            # 如果超出边界，或者当前位置是水('0')，就不用处理
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
                return
            
            # 把当前格子从陆地('1')变成水('0')，表示“已经访问过了”
            grid[r][c] = '0'

            # 递归处理四个方向的相邻格子（上下左右）
            dfs(r - 1, c)  # 上
            dfs(r + 1, c)  # 下
            dfs(r, c - 1)  # 左
            dfs(r, c + 1)  # 右

        count = 0  # 统计岛屿数量

        # 遍历整张地图
        for r in range(rows):
            for c in range(cols):
                # 如果当前格子是陆地，说明发现了一个新岛屿
                if grid[r][c] == '1':
                    count += 1        # 岛屿数量加一
                    dfs(r, c)         # 从这个点出发，淹掉整座岛
        
        return count  # 返回岛屿总数

javascript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length;

    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0')
            return
        
        grid[r][c] = '0';

        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }

    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                count++;
                dfs(r, c);
            }
        }
    }

    return count;
};

复杂度分析

时间复杂度：O(m * n)

空间复杂度：O(m * n)

链接

200 国际版

200 中文版