463. Island Perimeter

題目敘述

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

題目翻譯

題目會給一個二維陣列 grid，其內容表示一個島的地形狀況。1 表示為陸地、0 表示海洋。要計算這個島的周長是多少。這題比較好心的是，島中間並不會有 "湖"，所以可以忽略中間出現 0 的狀況。

解法解析

這題使用兩層迴圈來遍歷所有的元素，從左上 (0, 0) 一路到 右下 (m, n)，忽略 0 的元素只計算 1 的元素。只要是 1 就先加 4，之後再去判斷左側或上方是否有 1 的元素存在，如果有就扣掉 2，因為本身和旁邊的元素，都會有一個邊界被計算到，所以要扣掉 2。

Time complexity：O(mn) Space complexity：O(1)

程式範例

Python

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        perimeter = 0
        for i in range(len(grid)):
            for j, val in enumerate(grid[i]):
                if val:
                    perimeter += 4

                    if i > 0 and grid[i-1][j]:
                        perimeter -= 2
                    if j > 0 and grid[i][j - 1]:
                        perimeter -= 2
        return perimeter

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
    let perimeter = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j]) {
                perimeter += 4;

                if (i > 0 && grid[i - 1][j]) {
                    perimeter -= 2;
                }
                if (j > 0 && grid[i][j - 1]) {
                    perimeter -= 2;
                }
            }
        }
    }
    return perimeter;
};

Go

func islandPerimeter(grid [][]int) int {
    var perimeter int
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                perimeter += 4
                if i > 0 && grid[i-1][j] == 1 {
                    perimeter -= 2
                }
                if j > 0 && grid[i][j-1] == 1 {
                    perimeter -= 2
                }
            }
        }
    }
    return perimeter
}

Swift

class Solution {
    func islandPerimeter(_ grid: [[Int]]) -> Int {
        var perimeter = 0
        for ridx in 0..<grid.count {
            for cidx in 0..<grid[0].count {
                if grid[ridx][cidx] == 0 { continue }

                let prev = cidx > 0 && grid[ridx][cidx - 1] == 1 ? 2 : 0
                let top = ridx > 0 && grid[ridx - 1][cidx ] == 1 ? 2 : 0

                perimeter += 4 - (prev + top)
            }
        }
        return perimeter
    }
}

Kotlin

class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        var perimeter = 0
        for (i in grid.indices) {
            for (j in grid[i].indices) {
                if (grid[i][j] == 1) {
                    perimeter += 4
                    if (i > 0 && grid[i - 1][j] == 1) {
                        perimeter -= 2
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        perimeter -= 2
                    }
                }
            }
        }
        return perimeter
    }
}