LeetCode 463. 岛屿的周长

岛屿的周长问题是一个经典的深度优先搜索（DFS）题目。在这个问题中，我们需要计算一个由 1 和 0 组成的二维矩阵中岛屿的周长。

题目描述

给定一个由 0 和 1 组成的二维矩阵，其中 1 表示陆地，0 表示水域。计算岛屿的周长。

岛屿的周长是岛屿上所有边的长度之和，其中每条边与四个方向相邻（上下左右）。如果两条边相邻，则它们不会计入周长。

示例

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

输出: 16

解题思路

我们可以使用深度优先搜索（DFS）来解决这个问题。具体步骤如下：

1. 遍历矩阵中的每个元素。
2. 当遇到陆地（1）时，进入 DFS 函数。
3. 在 DFS 函数中，计算当前岛屿的周长，并递归地访问相邻的岛屿。
4. 每次访问相邻的岛屿时，如果相邻的岛屿也是陆地，则周长减去 2（因为相邻岛屿共享一条边）。
5. 最后，返回岛屿的总周长。

代码示例

以下是一个 Python 代码示例：

def islandPerimeter(grid):
    if not grid:
        return 0

    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
            return 1
        grid[i][j] = 0
        return (dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)) - 4

    perimeter = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                perimeter += dfs(i, j)
    return perimeter

# 测试代码
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(islandPerimeter(grid))  # 输出: 16

扩展阅读

如果你对深度优先搜索（DFS）感兴趣，可以阅读我们网站上的 DFS 相关文章。

[center]https://cloud-image.ullrai.com/q/Island_Perimeter/[/center]