树与图简单1 种解法

#463岛屿的周长

网格中只有一座不含湖泊的岛屿，计算陆地与海洋或边界接触的边数。

#矩阵#深度优先搜索#网格

解题主线

从任一陆地开始 DFS；递归走出网格或走到海洋时，恰好贡献一条周长边。

走到已访问陆地不贡献周长并返回 0，从而避免共享边被重复计算。

题目保证只有一座岛屿，因此找到第一块陆地并完成 DFS 后即可返回。

解法 1：按海陆边界计数的 DFS

从岛屿起点向四周递归，越界或遇海各返回 1，已访问陆地返回 0，四个方向之和即周长。

时间复杂度

O(mn) 最坏，每个陆地至多访问一次

空间复杂度

O(mn) 最坏，来自递归栈

463. 岛屿的周长 · 按海陆边界计数的 DFS

java

final class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                if (grid[row][column] == 1) {
                    return perimeter(grid, row, column);
                }
            }
        }
        return 0;
    }

    private int perimeter(int[][] grid, int row, int column) {
        if (row < 0 || row >= grid.length || column < 0 || column >= grid[0].length) {
            return 1;
        }
        if (grid[row][column] == 0) return 1;
        if (grid[row][column] != 1) return 0;

        grid[row][column] = 2;
        return perimeter(grid, row - 1, column)
            + perimeter(grid, row + 1, column)
            + perimeter(grid, row, column - 1)
            + perimeter(grid, row, column + 1);
    }
}

从岛屿起点向四周递归，越界或遇海各返回 1，已访问陆地返回 0，四个方向之和即周长。

边界与易错点

本题真实难度是简单。
必须先判断越界，再访问 grid[row][column]。
原地把陆地改为 2 会修改输入；重复调用同一网格无法得到原答案。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q_island_perimeter_463.java