資訊

• Question: 463. Island Perimeter
• From: Leetcode Daily Challenge 2024.04.18
• Difficulty: Easy

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度

---

題目

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

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

---

解法

概念

這題我對每個格子都看其左上角，只要是土地對海水或是海稅對土地，就會有邊界出現，如此走完 matrix 可以看完大部分的邊界，但有些卻漏的，例如最右邊、最下面看不到，而我又不希望重複看，所以就特別寫出來判斷了。最後要注意最上面跟最左邊因為 matrix 取值不要有取到 -1 的情況，要把 i, j == 0 的情況也抓出來先判斷。

程式碼

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = 0

        for i in range(0,m):
            for j in range(0,n):
                if grid[i][j] == 1:
                    # up
                    if i == 0:
                        ans += 1
                    elif grid[i-1][j] == 0:
                        ans += 1
                    # left
                    if j == 0:
                        ans += 1
                    elif grid[i][j-1] == 0:
                        ans += 1
                    # rightmost
                    if j == n-1:
                        ans += 1
                if grid[i][j] == 0:
                    if i > 0 and grid[i-1][j] == 1:
                        ans += 1
                    if j > 0 and grid[i][j-1] == 1:
                        ans += 1
        # buttom
        for j in range(len(grid[-1])):
            if grid[-1][j] == 1:
                ans += 1
        return ans

---

複雜度

時間複雜度

因為走訪完全部的 matrix，所以是

$O(mn)$

空間複雜度

沒有特別存什麼參數，所以是

$O(1)$