当前位置：首页 > ds >正文

岛屿周长问题的三种解法：直接计数法、数学计算法与深度优先搜索

ds 2025/7/6 12:33:07

问题描述

给定一个二维网格 grid，其中1表示陆地，0表示水域。网格中的格子水平和垂直方向相连（对角线不相连）。网格中恰好有一个岛屿（即一个或多个相连的陆地格子），需要计算这个岛屿的周长。

解法一：直接计数法（迭代法）

思路分析

这是最直观的解法：遍历网格中的每个格子，如果是陆地，初始周长为4。然后检查其上下左右四个方向的相邻格子：

每有一个相邻的陆地格子，周长减1
边界情况自动处理（边界外的格子视为水域）

代码实现

class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {int res = 0;int m = grid.size(), n = grid[0].size();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {int add = 4;    // 方格初始周长if(grid[i][j] == 1) {if(i - 1 >= 0 && grid[i - 1][j] == 1) add--; // 上if(i + 1 < m && grid[i + 1][j] == 1) add--;  // 下if(j - 1 >= 0 && grid[i][j - 1] == 1) add--; // 左if(j + 1 < n && grid[i][j + 1] == 1) add--;  // 右res += add;}}}return res;}
};

复杂度分析

时间复杂度：O(mn)，其中m和n分别是网格的行数和列数
空间复杂度：O(1)，仅使用常数级别的额外空间

解法二：数学计算法

思路分析

这种方法基于一个数学观察：

每个陆地格子贡献4条边
每对相邻的陆地格子共享一条边，会使总周长减少2条边

因此，岛屿周长 = 陆地格子数 × 4 - 相邻边数 × 2

代码实现

class Solution {public int islandPerimeter(int[][] grid) {int landCount = 0; // 陆地格子数量int adjacentCount = 0; // 相邻边数量for (int r = 0; r < grid.length; r++) {for (int c = 0; c < grid[0].length; c++) {if (grid[r][c] == 1) {landCount++;// 只检查右侧和下侧，避免重复计数if (c + 1 < grid[0].length && grid[r][c + 1] == 1) {adjacentCount++;}if (r + 1 < grid.length && grid[r + 1][c] == 1) {adjacentCount++;}}}}return landCount * 4 - adjacentCount * 2;}
}

复杂度分析

时间复杂度：O(mn)
空间复杂度：O(1)

解法三：深度优先搜索（DFS）

思路分析

使用深度优先搜索遍历岛屿：

当从陆地移动到边界或水域时，周长增加1
使用标记避免重复访问（将访问过的陆地标记为2）
递归探索四个方向（右、下、左、上）

代码实现

class Solution {constexpr static int dx[4] = {0, 1, 0, -1}; // 右、下、左、上constexpr static int dy[4] = {1, 0, -1, 0};public:int dfs(int x, int y, vector<vector<int>> &grid, int n, int m) {// 遇到边界或水域，贡献1条边if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {return 1;}// 已访问过的陆地，不贡献边if (grid[x][y] == 2) {return 0;}grid[x][y] = 2; // 标记为已访问int res = 0;// 探索四个方向for (int i = 0; i < 4; ++i) {int tx = x + dx[i];int ty = y + dy[i];res += dfs(tx, ty, grid, n, m);}return res;}int islandPerimeter(vector<vector<int>> &grid) {int n = grid.size(), m = grid[0].size();int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 1) {ans += dfs(i, j, grid, n, m);}}}return ans;}
};

复杂度分析

时间复杂度：O(mn)，每个格子最多访问一次
空间复杂度：O(mn)，递归调用栈的深度在最坏情况下可能达到网格大小

总结与对比

方法	优点	缺点	适用场景
直接计数法	直观易懂，实现简单	需要检查四个方向	小规模网格
数学计算法	效率高，仅需遍历一次	需要理解数学原理	所有规模网格
深度优先搜索	符合岛屿遍历的直觉，可扩展性强	需要递归，可能栈溢出	大规模连通岛屿或需要扩展功能