入口

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺備戰技術面試？力扣提供海量技術面試資源，幫助你高效提升編程技能，輕松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/island-perimeter/solutions/466248/dao-yu-de-zhou-chang-by-leetcode-solution/

題目描述

        給定一個 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 

解法一：迭代 

解題思路

        通過遍歷每個陸地格子，然后檢查它的上、右、下、左四個相鄰格子，?????????????如果越界或者相鄰格子是水域，就認為當前格子的周長增加了1。??????

java示例

class Solution {
    // 定義上、右、下、左四個方向的坐標偏移量
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public int islandPerimeter(int[][] grid) {
        int ans = 0;  // 用于累積島嶼的周長
        int n = grid.length;  // 網格的行數
        int m = grid[0].length;  // 網格的列數
        
        // 遍歷網格的每一個格子
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {  // ??????如果當前格子是陸地??????
                    for (int k = 0; k < 4; k++) {  // 遍歷四個方向
                        int tx = i + dx[k];  // 計算新的行坐標
                        int ty = j + dy[k];  // 計算新的列坐標

                        // 如果新坐標越界或者新坐標處是水域（0），則周長加一
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;  // 返回總周長
    }
}

代碼解釋

假設你站在一個島嶼的一個格子上（假設這個格子是陸地）。

• 你需要檢查當前格子的四個相鄰方向，即上、右、下、左。你會在這四個方向分別查看是否有相鄰的陸地格子或者是否超出了島嶼邊界。
• 對于每個方向，你執行以下操作：
  • 計算出當前方向上相鄰格子的坐標。如果你站在坐標 (i, j) 上，這個相鄰格子的坐標為 (i + dx[k], j + dy[k])，其中 k 表示方向（0 表示上、1 表示右、2 表示下、3 表示左）。
  • 檢查這個相鄰格子是否在島嶼邊界之外或者是否是水域（0）。如果是，那么周長需要增加1。
• 在每個方向上執行完上述操作后，你會得到一個在該方向上增加的周長值。
• 最后，將這四個方向上增加的周長值累加起來，就是當前格子所在的島嶼的總周長。
• 重復上述過程，將對每個格子的周長增加值都累加到 ans 變量中，最終得到整個島嶼的周長。

這個代碼段的關鍵是使用 dx 和 dy 數組，通過循環遍歷四個方向，然后根據每個方向的情況來計算周長的增加值。這種方法使得在處理不同方向時變得更加抽象和可讀，而不必在代碼中編寫大量的條件語句來處理每個方向的情況。 

復雜度分析

時間復雜度：O(nm)，其中 n 為網格的高度，m 為網格的寬度。

空間復雜度：O(1)