【LeetCode】463. 岛屿的周长

最新推荐文章于 2020-11-01 09:08:22 发布

jiiiiiaaaa

最新推荐文章于 2020-11-01 09:08:22 发布

阅读量369

点赞数

分类专栏： leetcode 文章标签： leetcode 算法

本文链接：https://blog.csdn.net/jiiiiiaaaa/article/details/109380247

版权

这篇博客介绍了如何解决LeetCode上的463题——岛屿的周长。提供了两种解题方法，包括迭代和深度优先搜索。在迭代法中，遍历每个陆地格子，检查其周围是否为边界或水域，累计周长。在深度优先搜索法中，通过DFS遍历并标记已访问的陆地格子来避免重复计数。时间复杂度均为O(nm)，其中n和m分别代表网格的高度和宽度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。

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

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

示例 :

输入:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

输出: 16

解释: 它的周长是下面图片中的 16 个黄色的边：

解题思路

方法一：迭代

思路与算法

对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。因此，我们可以遍历每个陆地格子，看其四个方向是否为边界或者水域，如果是，将这条边的贡献（即 1）加入答案 ans 中即可。

C++

class Solution {
    constexpr static int dx[4] = {0, 1, 0, -1};
    constexpr static int dy[4] = {1, 0, -1, 0};
publ

最低0.47元/天解锁文章