問題描述

給定一個二維網格?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. 直接計數法則提供了最直觀的實現參考

理解這三種解法的核心思想，能夠幫助我們在解決類似網格問題時靈活選擇最合適的策略。