一魚多吃: 從 島嶼周長 理解 圖論演算法的本質

今天的官方每日一題是Island Perimeter島嶼周長，很有趣的一題。
題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。

Zunnoon Ahmed on Unsplash

英文的題目敘述在這裡

題目敘述

題目會給我們一個二維陣列當作地圖，格子點為1代表陸地，格子點為0代表海洋。

要求我們以四連通N4的方式拜訪這座島嶼，並且計算這座島嶼的周長。

題目保證整張地圖只會有一座島嶼。

測試範例

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

row的總數 = 地圖的高度

• col == grid[i].length

col的總數 = 地圖的寬度

• 1 <= row, col <= 100

高度和寬度都介於 1~100之間。

• grid[i][j] is 0 or 1.

每個格子點一定是零(代表海洋)或一(代表陸地)。

• There is exactly one island in grid.

保證整張地圖只會有一座島嶼。

什麼時候會遇到島嶼的邊界?

當遇到陸地和海洋交界的時候。

當遇到地圖邊界的時候。

這時候剛好跨過島嶼的邊界，周長累加一。

用DFS 探索相連的陸地

先找出的第一塊陸地的格子點，接著用N4 四連通 配合深度優先DFS探索
周圍相鄰的陸地格子點。

當我們遇到陸地和海洋的交界，或者我們遇到地圖邊界時，
這時候剛好跨過島嶼的邊界，周長累加一。

時間複雜度O(H * W) 每個格子點最多拜訪一次。

空間複雜度O(H * W) 遞回深度最深是幾乎拜訪整張圖。

DFS 程式碼

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        H, W = len(grid), len(grid[0])

        def dfs(r, c):

            if not ( 0 <= r < H ) or not( 0 <= c < W) or grid[r][c] == 0:
                return 1

            if grid[r][c] == '#':
                return 0

            N4_offset = itertools.pairwise([0, 1, 0, -1, 0])
            
            perimeter = 0
            for dr, dc in N4_offset:
                nr, nc = r+dr, c+dc

                grid[r][c] = '#'
                perimeter += dfs(nr, nc)
            
            return perimeter

        # ==================================

        for r in range(H):
            for c in range(W):
                if grid[r][c] == 1:
                    return dfs(r, c)
                    
        return -1

用BFS 探索相連的陸地

先找出的第一塊陸地的格子點，接著用N4 四連通 配合廣度優先BFS探索
周圍相鄰的陸地格子點。

當我們遇到陸地和海洋的交界，或者我們遇到地圖邊界時，
這時候剛好跨過島嶼的邊界，周長累加一。

時間複雜度O(H * W) 每個格子點最多拜訪一次。

空間複雜度O(H * W) Queue長度最長是幾乎拜訪整張圖。

BFS 程式碼

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:

        H, W =len(grid), len(grid[0])

        perimeter = 0

        N4 = list( itertools.pairwise([0, 1, 0, -1, 0]) )

        for r in range(H):
            for c in range(W):
                if grid[r][c] == 1:
                    
                    bfs_queue = deque([(r,c)])

                    while bfs_queue:

                        cur_r, cur_c = bfs_queue.popleft()

                        #print(f"at {cur_r}, {cur_c}")

                        if not( 0 <= cur_r < H ) or not( 0 <= cur_c < W ) or grid[cur_r][cur_c] == 0:
                            # update perimeter count
                            perimeter += 1
                            continue

                        if grid[cur_r][cur_c] == '#':
                            # Avoid repeated traversal
                            continue

                        # Mark current grid as visited
                        grid[cur_r][cur_c] = '#'

                        for dr, dc in N4:
                            nr, nc = cur_r + dr, cur_c + dc
                            bfs_queue.append( (nr, nc) )
                            
                    return perimeter
                    
        return -1

依序掃描格子點的演算法

除了經典的DFS或者BFS探索演算法之外，我們也可以用掃描格子點的方式。

依序從左到右，從上到下掃描每個格子點。

統計遇到的陸地格子點數目，再統計內部邊緣(就是陸地和陸地相鄰的邊緣)有幾條。

每個陸地格子點會貢獻四條邊緣。
而內部邊緣會被兩塊相鄰的陸地所共用，所以重複計算了兩次。

最後，島嶼的周長

= 陸地格子點貢獻的邊緣數目 - 重複計算的內部邊緣

= 陸地格子點 * 4 - 內部邊緣總數 * 2

時間複雜度O(H * W) 每個格子點最多拜訪一次。

空間複雜度O(1) 只有使用固定尺寸的臨時變數，所需空間為常數級別。

依序掃描格子點的程式碼

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        h, w = len(grid), len(grid[0])
        
        if h * w == 0:
            # Quick response for simple case
            return 0
        
        land_cell, internal_edge = 0, 0
        
					# scan each cell from top to bottom, from left to right
        for y in range(h):
            for x in range(w):
                
                if grid[y][x] == 1:
											# current cell is land
                    land_cell += 1
        
                    if y and grid[y-1][x]:
														# current land cell share one internal edge with neighbor land cell on the top
                        internal_edge += 1
                    
                    if x and grid[y][x-1]:
														# current land cell share one internal edge with neighbor land cell of the left
                        internal_edge += 1
                        
						
				 # each land cell contributes 4 edge
        # each internal edge is repeatedly counted by 2 adjacent land cells
        perimeter = land_cell * 4 - internal_edge * 2
        
        return perimeter

關鍵知識點 找出共通模式

根據題意，找出島嶼邊緣的定義。

可以根據範例推敲發現:

當遇到陸地和海洋交界的時候。

當遇到地圖邊界的時候。

這時候剛好跨過島嶼的邊界，周長累加一。

結語

條條大路通羅馬，萬變不離其宗。

一個題目可以有好多種解法，但是背後核心觀念都是類似的。

只要掌握基本原理，根據題意，找出目標的明確定義，
接著採用合適的圖論演算法去計算所求(島嶼的周長)即可!

希望能幫助讀者、觀眾徹底理解基本圖論演算法BFS / DFS 的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~