一魚多吃: 從 島嶼周長 理解 圖論演算法的本質
今天的官方每日一題是Island Perimeter島嶼周長，很有趣的一題。
題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。
題目敘述
題目會給我們一個二維陣列當作地圖，格子點為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]is0or1.
每個格子點一定是零(代表海洋)或一(代表陸地)。
- 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 的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
