⛳圖論應用: 計算子島嶼的數量 Count Sub Islands_Leetcode #1905

Denys Nevozhai on Unsplash

題目敘述 1905. Count Sub Islands

給定兩個相同大小的二維陣列grid1, grid2。

格子點為0的地方代表海洋，格子點為1的地方代表陸地。

島嶼的定義是4連通(上、下、左、右)相鄰在一起的陸地。

如果有某個區域在grid2 是陸地而且在grid1也是陸地，
那麼這些區域就稱為「子島嶼」。

請問grid2裡有多少座子島嶼?

測試範例

Example 1:

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: 
紅色區域就是子島嶼，總共有3座。

Example 2:

Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2 
Explanation: 
紅色區域就是子島嶼，總共有2座。

約束條件

Constraints:

• m == grid1.length == grid2.length

m = 輸入陣列的高度

• n == grid1[i].length == grid2[i].length

n = 輸入陣列的寬度

• 1 <= m, n <= 500

輸入陣列的高度和寬度都介於1 ~ 500 之間

• grid1[i][j] and grid2[i][j] are either 0 or 1.

每個格子點都是1(陸地)或0(海洋)。

觀察

關鍵點在於如何計算「子島嶼」

實務上，圖論裡最常用演算法模板就是DFS 或者 BFS。

如果題目沒有特別指定，DFS寫起來比較直覺也比較簡單。

演算法 DFS先削去不一致的格子點，接著計算子島嶼。

第一步: 先消去grdi2上面不一致的格子點，
也就是grid2是陸地，但是在grid1是海洋的格子點。

第二步: 在grid2用DFS+四聯通計算子島嶼的數目，返回答案。

程式碼 DFS先削去不一致的格子點，接著計算子島嶼。

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
    
        m=len(grid1)
        n=len(grid1[0])
        
        def dfs(i,j):
            if i<0 or i>=m or j<0 or j>=n or grid2[i][j]==0:
                return
            
            grid2[i][j]=0
            dfs(i+1,j)
            dfs(i,j+1)
            dfs(i,j-1)
            dfs(i-1,j)
            return
            
        # removing all the gird cell which is land on grid2, water on grid1
        for i in range(m):
            for j in range(n):
                if grid2[i][j]==1 and grid1[i][j]==0:
                    dfs(i,j)
        
        sub_island=0
        # counting sub-islands
        for i in range(m):
            for j in range(n):
                if grid2[i][j]==1:
                    dfs(i,j)
                    sub_island+=1
        return sub_island
	

複雜度分析

時間複雜度: O(mn)

所有格子點最多掃描兩次，總共有O(mn)個格子點。

空間複雜度: O(mn)

所有格子點最多掃描兩次，總共有O(mn)個格子點，遞迴最大深度為O(mn)。

Reference:

[1] Count Sub Islands - LeetCode