463. 岛屿的周长 - Island Perimeter

🎯 问题描述（来源于LeetCode）

描述：
给定一个 m x n 的二维网格 grid，其中 1 表示陆地，0 表示水域。
网格中的格子是水平或垂直相连的（四方向）。假设整个网格被水完全包围，且只有一个岛屿（即所有陆地格子是连通的，且没有“洞”）。
请计算该岛屿的周长。

说明：

一个格子的周长贡献取决于它四条边中，相邻格子为水域或边界的情况。
岛屿不会包含内陆湖（但此题假设没有洞）。

示例：

示例 1：

1 2	输入: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] 输出: 16

示例 2：

1 2	输入: grid = [[1]] 输出: 4

💻 解题思路

思路1：遍历每个陆地格子，统计边界边数

算法步骤

初始化：获取网格尺寸 m, n；定义四方向偏移量；答案 ans = 0。
遍历所有格子：若 grid[i][j] == 1，调用辅助函数计算该格子贡献的周长。
辅助函数 dfs(x, y)：对四个方向检查邻居是否越界或为水域，若是则计数加一；返回计数。
累加：将所有陆地格子的贡献累加到 ans。
返回 ans。

思路1：代码实现

from typing import List

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        direction = [(-1,0), (0,-1), (1,0), (0,1)]
        
        def cnt_boundary(x, y):
            cnt = 0
            for dx, dy in direction:
                di, dj = x + dx, y + dy
                if di < 0 or di >= m or dj < 0 or dj >= n or grid[di][dj] == 0:
                    cnt += 1
            return cnt
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans += cnt_boundary(i, j)
        return ans

思路1：📊 性能分析

时间复杂度： $O(m \times n)$ ，每个格子至多访问一次，每个陆地格子检查 4 个方向。
空间复杂度： $O(1)$ ，仅使用常数额外空间。

思路2：DFS 递归计算周长（原地标记）

算法步骤

初始化：获取网格尺寸 m, n；定义四方向偏移量。
定义 DFS 函数 dfs(x, y)：
- 递归终止条件（返回 1 的情况）：
  - 如果 (x, y) 越界，或 grid[x][y] == 0（遇到水域），说明当前方向是一条边界边，返回 1。
- 重复访问处理：如果 grid[x][y] != 1（即已经标记为 2 或其他值），说明该格子已被访问过，返回 0（不重复计数）。
- 标记已访问：将 grid[x][y] 设为 2（表示已访问的陆地）。
- 递归累加：返回四个方向上 dfs 返回值的总和。
寻找起点：遍历网格，找到第一个陆地格子 (i, j)，调用 dfs(i, j) 并直接返回其结果（因为题目保证只有一个岛屿）。

思路2：代码实现

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        direction = [(-1,0), (0,-1), (1,0), (0,1)]
        
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return 1
            if grid[x][y] != 1:
                return 0
            grid[x][y] = 2
            return (dfs(x+1, y) + dfs(x-1, y) + 
                    dfs(x, y+1) + dfs(x, y-1))
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j)
        return 0

思路2：📊 性能分析

时间复杂度： $O(m \times n)$ ，每个陆地格子恰好访问一次，每个格子最多检查四个方向。
空间复杂度： $O(L)$ ，其中 $L$ 为岛屿的陆地格子数量（递归栈深度等于岛屿大小，最坏情况 $O(m \times n)$ ）。

思路对比与思考

思路1 直接、简单，不修改原网格，无需递归，适合所有情况。
思路2 利用 DFS 遍历整个岛屿并递归累加边界，代码更简洁，但会修改原网格（标记为2），且依赖递归深度（Python 默认递归限制可能导致栈溢出，如果岛屿过大需注意）。
两种方法均只需遍历一次网格，性能相近。推荐在面试或实际编码中使用思路1，因为不修改输入且无递归风险。