岛屿数量

题目描述

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

示例 3：

输入: grid = [['1']]
输出: 1

示例 4：

输入: grid = [['0']]
输出: 0

解题思路

采用淹没法（Flood Fill）：

DFS 版本：

1. 遍历网格，每遇到一个 '1'，岛屿计数 +1。
2. 从该位置开始 DFS，将与之相连的所有 '1' 变为 '0'（淹没），表示该岛屿已被访问。
3. 继续遍历，重复上述过程。

BFS 版本：将 DFS 递归替换为队列 BFS，思路相同。

代码实现

// 方向数组：右、左、下、上
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

/**
 * 方法一：DFS 版（淹没法）
 * @param {string[][]} grid - 二维字符数组
 * @returns {number} 岛屿数量
 */
function numIslandsDFS(grid) {
    const rows = grid.length;
    if (!rows) return 0;
    const cols = grid[0].length;
    let count = 0;

    const dfs = (x, y) => {
        if (x < 0 || x >= cols || y < 0 || y >= rows || grid[y][x] === '0') {
            return;
        }
        grid[y][x] = '0';        // 淹没当前陆地
        dfs(x + 1, y);           // 四方向递归
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                count++;          // 遇到新岛屿，计数
                dfs(j, i);        // 淹没整个岛
            }
        }
    }
    return count;
}

/**
 * 方法二：BFS 版
 * @param {string[][]} grid - 二维字符数组
 * @returns {number} 岛屿数量
 */
function numIslandsBFS(grid) {
    const rows = grid.length;
    if (!rows) return 0;
    const cols = grid[0].length;
    let count = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '0') continue;

            count++;
            const queue = [[j, i]];
            grid[i][j] = '0';

            while (queue.length > 0) {
                const [x, y] = queue.shift();
                for (const [dx, dy] of DIRS) {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && grid[ny][nx] === '1') {
                        grid[ny][nx] = '0';
                        queue.push([nx, ny]);
                    }
                }
            }
        }
    }
    return count;
}

复杂度分析

• 时间复杂度：O(m × n)，每个格子最多访问一次。
• 空间复杂度：DFS 为 O(m × n)，最坏情况递归栈深度为整个网格大小；BFS 为 O(min(m, n))，队列中最多存储一条对角线的格子数。

grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]

3