200.岛屿数量

LeetCode LeetCode 深度优先搜索 广度优先搜索 热题100 岛屿
发布时间 :
字数:2.7k 阅读 : 评论:
  1. 200.岛屿数量
    1. 200.1 题目
    2. 200.2 题解
      1. 方法一：深度优先搜索（DFS）
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：广度优先搜索（BFS）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 200.3 代码
    4. 200.4 运行结果

200.岛屿数量

200.1 题目

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

200.2 题解

方法一：深度优先搜索（DFS）

思路

遍历网格，遇到 '1'（陆地）时，岛屿数量加1，然后用 DFS 把这个岛屿「淹没」——把所有相连的陆地都标记为 '0'。

这样做的妙处：每发现一个新岛屿，就把它完全消灭，后面就不会重复计数了。

DFS 访问上下左右四个方向，把所有相连的陆地都变成水。

举个例子：

1 1 0
1 0 0
0 0 1
  • 遍历到(0,0)，发现陆地，count=1，DFS淹没整个左上角岛屿
  • 继续遍历，(0,1)、(1,0)已经是水了
  • 遍历到(2,2)，发现陆地，count=2，DFS淹没
  • 最终结果：2个岛屿

复杂度分析

  • 时间复杂度：O(m × n)
  • 空间复杂度：O(m × n)，递归栈深度

代码

// 方法一：深度优先搜索（DFS）
// 遍历网格，遇到陆地时岛屿数+1，然后通过DFS将该岛屿所有相连的陆地标记为水（避免重复计数）
static int NumIslandsDFS(char[][] grid)
{
    if (grid == null || grid.Length == 0) return 0;

    int count = 0;
    int rows = grid.Length;
    int cols = grid[0].Length;

    // 遍历网格中的每个单元格
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            // 如果遇到陆地，岛屿数+1，并通过DFS将该岛屿所有陆地标记为水
            if (grid[i][j] == '1')
            {
                count++;
                DFS(grid, i, j);
            }
        }
    }

    return count;
}

// DFS辅助方法：将当前陆地及其相连的所有陆地标记为水
static void DFS(char[][] grid, int i, int j)
{
    int rows = grid.Length;
    int cols = grid[0].Length;

    // 边界检查：如果超出网格范围或当前不是陆地，直接返回
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1')
        return;

    // 将当前陆地标记为水（避免重复访问）
    grid[i][j] = '0';

    // 递归访问上下左右四个方向
    DFS(grid, i - 1, j); // 上
    DFS(grid, i + 1, j); // 下
    DFS(grid, i, j - 1); // 左
    DFS(grid, i, j + 1); // 右
}

方法二：广度优先搜索（BFS）

思路

遍历网格，遇到 '1'（陆地）时，岛屿数量加1，然后用 BFS 把这个岛屿「淹没」。

使用队列：将当前陆地入队，然后不断出队并检查四个方向的邻居，如果是陆地则入队并标记为 '0'。

与 DFS 的区别：DFS 用递归栈，BFS 用显式队列。

举个例子：

1 1 0
1 0 0
0 0 1
  • 遍历到(0,0)，count=1，BFS：(0,0)入队 → 出队，邻居(0,1)、(1,0)入队 → 标记为0
  • 继续遍历，(0,1)、(1,0)已经是水了
  • 遍历到(2,2)，count=2，BFS淹没
  • 结果：2个岛屿

复杂度分析

  • 时间复杂度：O(m × n)
  • 空间复杂度：O(min(m, n))，队列

代码

// 方法二：广度优先搜索（BFS）
// 遍历网格，遇到陆地时岛屿数+1，然后通过BFS将该岛屿所有相连的陆地标记为水（避免重复计数）
static int NumIslandsBFS(char[][] grid)
{
    if (grid == null || grid.Length == 0) return 0;

    int count = 0;
    int rows = grid.Length;
    int cols = grid[0].Length;

    // 遍历网格中的每个单元格
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            // 如果遇到陆地，岛屿数+1，并通过BFS将该岛屿所有陆地标记为水
            if (grid[i][j] == '1')
            {
                count++;
                BFS(grid, i, j);
            }
        }
    }

    return count;
}

// BFS辅助方法：将当前陆地及其相连的所有陆地标记为水
static void BFS(char[][] grid, int i, int j)
{
    int rows = grid.Length;
    int cols = grid[0].Length;

    // 使用队列存储待访问的陆地坐标
    Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
    queue.Enqueue(new Tuple<int, int>(i, j));
    // 先将当前陆地标记为水
    grid[i][j] = '0';

    // 定义四个方向：上、下、左、右
    int[][] directions = new int[][] {
        new int[] {-1, 0}, // 上
        new int[] {1, 0},  // 下
        new int[] {0, -1}, // 左
        new int[] {0, 1}   // 右
    };

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        int currRow = current.Item1;
        int currCol = current.Item2;

        // 遍历四个方向
        foreach (var dir in directions)
        {
            int newRow = currRow + dir[0];
            int newCol = currCol + dir[1];

            // 检查新坐标是否在网格范围内且为陆地
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1')
            {
                // 标记为水并入队
                grid[newRow][newCol] = '0';
                queue.Enqueue(new Tuple<int, int>(newRow, newCol));
            }
        }
    }
}

200.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        #endregion

        #region 测试

        // 示例 1
        char[][] grid1 = new char[][] {
            new char[] {'1','1','1','1','0'},
            new char[] {'1','1','0','1','0'},
            new char[] {'1','1','0','0','0'},
            new char[] {'0','0','0','0','0'}
        };
        int result1 = NumIslandsDFS(CloneGrid(grid1));
        Console.WriteLine($"示例1 DFS 方法 输出：{result1}");
        int result1_2 = NumIslandsBFS(CloneGrid(grid1));
        Console.WriteLine($"示例1 BFS 方法 输出：{result1_2}");

        // 示例 2
        char[][] grid2 = new char[][] {
            new char[] {'1','1','0','0','0'},
            new char[] {'1','1','0','0','0'},
            new char[] {'0','0','1','0','0'},
            new char[] {'0','0','0','1','1'}
        };
        int result2 = NumIslandsDFS(CloneGrid(grid2));
        Console.WriteLine($"示例2 DFS 方法 输出：{result2}");
        int result2_2 = NumIslandsBFS(CloneGrid(grid2));
        Console.WriteLine($"示例2 BFS 方法 输出：{result2_2}");

        #endregion
    }

    #region 辅助方法

    // 辅助方法：克隆网格，避免测试时修改原网格
    static char[][] CloneGrid(char[][] grid)
    {
        if (grid == null) return null;
        char[][] clone = new char[grid.Length][];
        for (int i = 0; i < grid.Length; i++)
        {
            clone[i] = (char[])grid[i].Clone();
        }
        return clone;
    }

    #endregion

    #region 答案

    // 方法一：深度优先搜索（DFS）
    // 遍历网格，遇到陆地时岛屿数+1，然后通过DFS将该岛屿所有相连的陆地标记为水（避免重复计数）
    static int NumIslandsDFS(char[][] grid)
    {
        if (grid == null || grid.Length == 0) return 0;

        int count = 0;
        int rows = grid.Length;
        int cols = grid[0].Length;

        // 遍历网格中的每个单元格
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                // 如果遇到陆地，岛屿数+1，并通过DFS将该岛屿所有陆地标记为水
                if (grid[i][j] == '1')
                {
                    count++;
                    DFS(grid, i, j);
                }
            }
        }

        return count;
    }

    // DFS辅助方法：将当前陆地及其相连的所有陆地标记为水
    static void DFS(char[][] grid, int i, int j)
    {
        int rows = grid.Length;
        int cols = grid[0].Length;

        // 边界检查：如果超出网格范围或当前不是陆地，直接返回
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1')
            return;

        // 将当前陆地标记为水（避免重复访问）
        grid[i][j] = '0';

        // 递归访问上下左右四个方向
        DFS(grid, i - 1, j); // 上
        DFS(grid, i + 1, j); // 下
        DFS(grid, i, j - 1); // 左
        DFS(grid, i, j + 1); // 右
    }

    // 方法二：广度优先搜索（BFS）
    // 遍历网格，遇到陆地时岛屿数+1，然后通过BFS将该岛屿所有相连的陆地标记为水（避免重复计数）
    static int NumIslandsBFS(char[][] grid)
    {
        if (grid == null || grid.Length == 0) return 0;

        int count = 0;
        int rows = grid.Length;
        int cols = grid[0].Length;

        // 遍历网格中的每个单元格
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                // 如果遇到陆地，岛屿数+1，并通过BFS将该岛屿所有陆地标记为水
                if (grid[i][j] == '1')
                {
                    count++;
                    BFS(grid, i, j);
                }
            }
        }

        return count;
    }

    // BFS辅助方法：将当前陆地及其相连的所有陆地标记为水
    static void BFS(char[][] grid, int i, int j)
    {
        int rows = grid.Length;
        int cols = grid[0].Length;

        // 使用队列存储待访问的陆地坐标
        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
        queue.Enqueue(new Tuple<int, int>(i, j));
        // 先将当前陆地标记为水
        grid[i][j] = '0';

        // 定义四个方向：上、下、左、右
        int[][] directions = new int[][] {
            new int[] {-1, 0}, // 上
            new int[] {1, 0},  // 下
            new int[] {0, -1}, // 左
            new int[] {0, 1}   // 右
        };

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            int currRow = current.Item1;
            int currCol = current.Item2;

            // 遍历四个方向
            foreach (var dir in directions)
            {
                int newRow = currRow + dir[0];
                int newCol = currCol + dir[1];

                // 检查新坐标是否在网格范围内且为陆地
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1')
                {
                    // 标记为水并入队
                    grid[newRow][newCol] = '0';
                    queue.Enqueue(new Tuple<int, int>(newRow, newCol));
                }
            }
        }
    }

    #endregion
}

200.4 运行结果

示例1 DFS 方法 输出：1
示例1 BFS 方法 输出：1
示例2 DFS 方法 输出：3
示例2 BFS 方法 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏