題目:

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.

給定一二維陣列作為一座島的地圖,1表陸地,0表水
回傳該島的周長

我遍歷整個二維陣列來計算周長

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row=len(grid)
        column=len(grid[0])
        ans=0
        
        for i,m in enumerate(grid):
            for j,n in enumerate(m):
                if n==0:
                    continue
                    
                plus=4
                
                if i>0 and grid[i-1][j]==1:
                    plus=plus-1
                if i<row-1 and grid[i+1][j]==1:
                    plus=plus-1
                if j>0 and grid[i][j-1]==1:
                    plus=plus-1
                if j<column-1 and grid[i][j+1]==1:
                    plus=plus-1
                    
                ans=ans+plus
                  
        return ans

一塊陸地最多可以提供長度四的周長,但那也要它四面環水
若一邊連接陸地其提供的周長便會少1

於是我開始遍歷所有陣列元素
水不提供周長,直接略過
陸地先假設它會提供4的周長(plus)
而其四面每有一面是陸地就將plus-1
最後加到ans上,完全遍歷完後回傳ans
最後執行時間517ms(faster than 94.13%)

在討論區,我有看到遞迴的做法如下

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        visit=set()
        
        def dfs(i,j):
            if i>=len(grid) or j>=len(grid[0]) or i<0 or j<0 or grid[i][j]==0:
                return 1
            if (i,j) in visit:
                return 0
            
            visit.add((i,j))
            
            return dfs(i,j+1)+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j-1) 
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    return dfs(i,j)

由於題目確定島只有一座
所以我們可以藉由一塊陸地擴張找出島的周長

以一塊陸地為起始,往上下左右擴張
紀錄每個走過的土地
若為沒走過的陸地則繼續上下左右擴張
若為走過的陸地不繼續擴張,回傳0
若為水或地圖邊界則表示我們找到了島的邊界,回傳1
找到的邊界總和即為島的周長
最後執行時間645ms(faster than 80.11%)

那我們下題見