463.岛屿的周长

LeetCode LeetCode 数组 深度优先搜索 广度优先搜索 矩阵
发布时间 :
字数:3.1k 阅读 : 评论:
  1. 463.岛屿的周长
    1. 463.1 题目
    2. 463.2 题解
      1. 方法一：遍历计算周长
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：深度优先遍历计算周长
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：统计相邻岛屿
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 463.3 代码
    4. 463.4 运行结果

463.岛屿的周长

463.1 题目

给定一个 row x col 的二维网格地图 grid，其中：
grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖”指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

输入：grid = [[1,0]]
输出：4

提示：

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 100
  • grid[i][j] 为 0 或 1

463.2 题解

方法一：遍历计算周长

思路

遍历二维数组，对于每个岛屿格子，检查其上下左右四个方向。如果某个方向是边界或水域，则该方向贡献一条边（周长加1）。累加所有岛屿格子的边数即为总周长。

核心思想：每个陆地格子贡献的周长 = 4 - 相邻陆地格子数。

具体步骤：

  1. 遍历二维数组。
  2. 对于每个岛屿格子（值为 1）：
    • 检查上、下、左、右四个方向
    • 如果是边界或水域，周长加 1
  3. 返回总周长。

举例：对于 grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]：

  • 格子 (0,1)：上边界、左水域、右水域、下陆地 → 贡献 3 条边
  • 格子 (1,0)：左边界、上水域、下水域、右陆地 → 贡献 3 条边
  • 格子 (1,1)：上陆地、下陆地、左陆地、右陆地 → 贡献 0 条边
  • 格子 (1,2)：上水域、下水域、左陆地、右水域 → 贡献 3 条边
  • …累加所有格子
  • 结果：16

复杂度分析

  • 时间复杂度：O(m × n)，遍历整个网格。
  • 空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：遍历计算周长
// 遍历二维数组，如果当前位置是岛屿，判断上下左右是否超出边界或者是水域，是的话加周长
static int IslandPerimeter1(int[][] grid)
{
    int perimeter = 0; // 初始化周长

    // 遍历二维数组
    for (int i = 0; i < grid.Length; i++)
    {
        for (int j = 0; j < grid[i].Length; j++)
        {
            // 如果当前位置是岛屿（值为1）
            if (grid[i][j] == 1)
            {
                // 上边
                if (i == 0 || grid[i - 1][j] == 0)
                    perimeter++; // 如果上边是水域，贡献周长
                // 下边
                if (i == grid.Length - 1 || grid[i + 1][j] == 0)
                    perimeter++; // 如果下边是水域，贡献周长
                // 左边
                if (j == 0 || grid[i][j - 1] == 0)
                    perimeter++; // 如果左边是水域，贡献周长
                // 右边
                if (j == grid[i].Length - 1 || grid[i][j + 1] == 0)
                    perimeter++; // 如果右边是水域，贡献周长
            }
        }
    }

    return perimeter; // 返回最终周长
}

方法二：深度优先遍历计算周长

思路

使用 DFS 遍历岛屿，遇到边界或水域时返回 1（贡献一条边）。

已访问的格子标记为 -1，避免重复计算。递归计算四个方向的周长贡献并累加。

举个例子：

1 1
1 1
  • DFS从(0,0)开始
  • (0,0)：上边界贡献1，左边界贡献1，继续DFS
  • (0,1)：上边界贡献1，右边界的邻居(0,2)越界贡献1
  • …最终累加得到8

复杂度分析

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

代码

// 方法二：深度优先遍历计算周长
// 遍历二维数组，如果当前位置是岛屿，进行深度优先遍历，
// 判断是否越界或当前位置为水域
// 如果当前位置已访问过，返回0表示不再计算周长
// 标记当前位置已访问,递归的对上下左右进行深度优先遍历变量
static int IslandPerimeter2(int[][] grid)
{
    int perimeter = 0; // 初始化周长

    // 遍历二维数组
    for (int i = 0; i < grid.Length; i++)
    {
        for (int j = 0; j < grid[i].Length; j++)
        {
            // 如果当前位置是岛屿（值为1）
            if (grid[i][j] == 1)
            {
                // 调用DFS函数计算周长并累加
                perimeter += DFS(grid, i, j);
            }
        }
    }

    return perimeter; // 返回最终周长
}

// 深度优先搜索
static int DFS(int[][] grid, int i, int j)
{
    // 判断是否越界或当前位置为水域
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == 0)
    {
        return 1; // 返回1表示贡献周长
    }

    // 当前不为水域 如果当前位置已访问过
    if (grid[i][j] == -1)
    {
        return 0; // 返回0表示不再计算周长
    }

    // 这个岛访问过了 标记当前位置已访问
    grid[i][j] = -1;

    int perimeter = 0;

    // 递归调用DFS，计算上下左右的周长并累加
    perimeter += DFS(grid, i - 1, j);
    perimeter += DFS(grid, i + 1, j);
    perimeter += DFS(grid, i, j - 1);
    perimeter += DFS(grid, i, j + 1);

    return perimeter; // 返回当前位置的周长贡献
}

方法三：统计相邻岛屿

思路

每个岛屿格子初始贡献 4 条边。

如果与上方格子相邻，两边各减 1（共减 2）。
如果与左方格子相邻，两边各减 1（共减 2）。

只需检查上方和左方，避免重复计算。

举个例子：

1 1
1 1
  • (0,0)：贡献4
  • (0,1)：上方无，左方有，贡献4-2=2
  • (1,0)：上方有，左方无，贡献4-2=2
  • (1,1)：上方有，左方有，贡献4-4=0
  • 总周长：4+2+2+0=8

复杂度分析

  • 时间复杂度：O(m × n)
  • 空间复杂度：O(1)

代码

// 方法三：统计相邻岛屿
// 遍历二维数组，对每个岛屿位置检查其上下左右是否也是岛屿，如果是，则当前岛屿的周长减1。
static int IslandPerimeter3(int[][] grid)
{
    int count = 0; // 初始化周长

    // 遍历二维数组
    for (int i = 0; i < grid.Length; i++)
    {
        for (int j = 0; j < grid[i].Length; j++)
        {
            // 如果当前位置是岛屿（值为1）
            if (grid[i][j] == 1)
            {
                // 调用GetCurEdge函数计算当前岛屿的周长并累加
                count += GetCurEdge(grid, i, j);
            }
        }
    }

    return count; // 返回最终周长
}

// 获取当前岛屿的周长
static int GetCurEdge(int[][] grid, int x, int y)
{
    int result = 4; // 初始化周长
    // 分别检查当前岛屿的上下左右是否也是岛屿，如果是，则周长减1
    if (x - 1 >= 0 && grid[x - 1][y] == 1)
    {
        result--; // 上方是岛屿，周长减1
    }

    if (x + 1 < grid.Length && grid[x + 1][y] == 1)
    {
        result--; // 下方是岛屿，周长减1
    }

    if (y - 1 >= 0 && grid[x][y - 1] == 1)
    {
        result--; // 左侧是岛屿，周长减1
    }

    if (y + 1 < grid[x].Length && grid[x][y + 1] == 1)
    {
        result--; // 右侧是岛屿，周长减1
    }

    return result; // 返回当前岛屿的周长
}

463.3 代码

using System;

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

        // 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
        // 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿。
        // 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。
        // 网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

        // 示例 1：
        // 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
        // 输出：16
        // 解释：它的周长是上面图片中的 16 个黄色的边

        // 示例 2：
        // 输入：grid = [[1]]
        // 输出：4

        // 示例 3：
        // 输入：grid = [[1,0]]
        // 输出：4

        // 提示：
        // row == grid.length
        // col == grid[i].length
        // 1 <= row, col <= 100
        // grid[i][j] 为 0 或 1

        #endregion

        #region 测试

        // 示例 1
        int[][] grid1 = new int[][]
        {
            new int[] { 0, 1, 0, 0 },
            new int[] { 1, 1, 1, 0 },
            new int[] { 0, 1, 0, 0 },
            new int[] { 1, 1, 0, 0 }
        };
        int result1_1 = IslandPerimeter1(grid1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = IslandPerimeter2(grid1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[][] grid2 = new int[][]
        {
            new int[] { 1 }
        };
        int result2_1 = IslandPerimeter1(grid2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = IslandPerimeter2(grid2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int[][] grid3 = new int[][]
        {
            new int[] { 1, 0 }
        };
        int result3_1 = IslandPerimeter1(grid3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        int result3_2 = IslandPerimeter2(grid3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：遍历计算周长
    // 遍历二维数组，如果当前位置是岛屿，判断上下左右是否超出边界或者是水域，是的话加周长
    static int IslandPerimeter1(int[][] grid)
    {
        int perimeter = 0; // 初始化周长

        // 遍历二维数组
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                // 如果当前位置是岛屿（值为1）
                if (grid[i][j] == 1)
                {
                    // 上边
                    if (i == 0 || grid[i - 1][j] == 0)
                        perimeter++; // 如果上边是水域，贡献周长
                    // 下边
                    if (i == grid.Length - 1 || grid[i + 1][j] == 0)
                        perimeter++; // 如果下边是水域，贡献周长
                    // 左边
                    if (j == 0 || grid[i][j - 1] == 0)
                        perimeter++; // 如果左边是水域，贡献周长
                    // 右边
                    if (j == grid[i].Length - 1 || grid[i][j + 1] == 0)
                        perimeter++; // 如果右边是水域，贡献周长
                }
            }
        }

        return perimeter; // 返回最终周长
    }

    // 方法二：深度优先遍历计算周长
    // 遍历二维数组，如果当前位置是岛屿，进行深度优先遍历，
    // 判断是否越界或当前位置为水域
    // 如果当前位置已访问过，返回0表示不再计算周长
    // 标记当前位置已访问,递归的对上下左右进行深度优先遍历变量
    static int IslandPerimeter2(int[][] grid)
    {
        int perimeter = 0; // 初始化周长

        // 遍历二维数组
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                // 如果当前位置是岛屿（值为1）
                if (grid[i][j] == 1)
                {
                    // 调用DFS函数计算周长并累加
                    perimeter += DFS(grid, i, j);
                }
            }
        }

        return perimeter; // 返回最终周长
    }

    // 深度优先搜索
    static int DFS(int[][] grid, int i, int j)
    {
        // 判断是否越界或当前位置为水域
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == 0)
        {
            return 1; // 返回1表示贡献周长
        }

        // 当前不为水域 如果当前位置已访问过
        if (grid[i][j] == -1)
        {
            return 0; // 返回0表示不再计算周长
        }

        // 这个岛访问过了 标记当前位置已访问
        grid[i][j] = -1;

        int perimeter = 0;

        // 递归调用DFS，计算上下左右的周长并累加
        perimeter += DFS(grid, i - 1, j);
        perimeter += DFS(grid, i + 1, j);
        perimeter += DFS(grid, i, j - 1);
        perimeter += DFS(grid, i, j + 1);

        return perimeter; // 返回当前位置的周长贡献
    }

    // 方法三：遍历计算周长
    // 遍历二维数组，对每个岛屿位置检查其上下左右是否也是岛屿，如果是，则当前岛屿的周长减1。
    static int IslandPerimeter3(int[][] grid)
    {
        int count = 0; // 初始化周长

        // 遍历二维数组
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                // 如果当前位置是岛屿（值为1）
                if (grid[i][j] == 1)
                {
                    // 调用GetCurEdge函数计算当前岛屿的周长并累加
                    count += GetCurEdge(grid, i, j);
                }
            }
        }

        return count; // 返回最终周长
    }

    // 获取当前岛屿的周长
    static int GetCurEdge(int[][] grid, int x, int y)
    {
        int result = 4; // 初始化周长
        // 分别检查当前岛屿的上下左右是否也是岛屿，如果是，则周长减1
        if (x - 1 >= 0 && grid[x - 1][y] == 1)
        {
            result--; // 上方是岛屿，周长减1
        }

        if (x + 1 < grid.Length && grid[x + 1][y] == 1)
        {
            result--; // 下方是岛屿，周长减1
        }

        if (y - 1 >= 0 && grid[x][y - 1] == 1)
        {
            result--; // 左侧是岛屿，周长减1
        }

        if (y + 1 < grid[x].Length && grid[x][y + 1] == 1)
        {
            result--; // 右侧是岛屿，周长减1
        }

        return result; // 返回当前岛屿的周长
    }

    #endregion
}

463.4 运行结果

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

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏