树与图简单1 种解法
#463岛屿的周长
网格中只有一座不含湖泊的岛屿，计算陆地与海洋或边界接触的边数。
#矩阵#深度优先搜索#网格
原题
给定一个 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.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]为0或1
解题主线
- 从任一陆地开始 DFS；递归走出网格或走到海洋时，恰好贡献一条周长边。
- 走到已访问陆地不贡献周长并返回 0，从而避免共享边被重复计算。
- 题目保证只有一座岛屿，因此找到第一块陆地并完成 DFS 后即可返回。
解法 1：按海陆边界计数的 DFS
从岛屿起点向四周递归，越界或遇海各返回 1，已访问陆地返回 0，四个方向之和即周长。
-
时间复杂度： O(mn) 最坏，每个陆地至多访问一次
-
空间复杂度： O(mn) 最坏，来自递归栈
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);
}
}边界与易错点
- 本题真实难度是简单。
- 必须先判断越界，再访问 grid[row][column]。
- 原地把陆地改为 2 会修改输入；重复调用同一网格无法得到原答案。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/medium/Q_island_perimeter_463.java