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

问题描述

给定一个二维网格 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)，仅使用常数级别的额外空间

解法二：数学计算法

思路分析

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

1. 每个陆地格子贡献4条边

2. 每对相邻的陆地格子共享一条边，会使总周长减少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. 当从陆地移动到边界或水域时，周长增加1

2. 使用标记避免重复访问（将访问过的陆地标记为2）

3. 递归探索四个方向（右、下、左、上）

代码实现

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)，递归调用栈的深度在最坏情况下可能达到网格大小

总结与对比

在实际应用中：

1. 对于简单场景，数学计算法通常是最优选择，高效且简洁

2. 当需要扩展功能（如计算多个岛屿）时，DFS更具扩展性

3. 直接计数法则提供了最直观的实现参考

理解这三种解法的核心思想，能够帮助我们在解决类似网格问题时灵活选择最合适的策略。