463.岛屿的周长

LeetCode LeetCode 深度优先搜索 广度优先搜索 数组 矩阵
发布时间 :
字数:2.5k 阅读 : 评论:
  1. 463.岛屿的周长
    1. 463.1 题目
    2. 463.2 题解
      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 题解

遍历计算周长

// 方法一：遍历计算周长
// 遍历二维数组，如果当前位置是岛屿，判断上下左右是否超出边界或者是水域，是的话加周长
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; // 返回当前岛屿的周长
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏