Medium
Related Topics: Array / Depth-First Search / Breadth-First Search / Union Find / Matrix
LeetCode Source

解題想法

DFS 遍歷：

首先，定義一個深度優先搜索（DFS）函數，用來遍歷和標記 grid2 中的島嶼。

之後，遍歷 grid2，對於 grid2 中的每個 1（代表島嶼），如果 grid1 中對應位置是 0，則使用 DFS 將該島嶼標記為 0，因為它不可能是子島嶼。

最後再次遍歷 grid2，對於仍然是 1 的格子（即可能的子島嶼），使用 DFS 遍歷整個島嶼並計數。

Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Python

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)
        
    for i in range(m):
        for j in range(n):
            if grid2[i][j]==1 and grid1[i][j]==0:
                dfs(i,j)
    
    c=0

    for i in range(m):
        for j in range(n):
            if grid2[i][j]==1:
                dfs(i,j)
                c+=1
    return c

C++

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid1.size();
        int n = grid1[0].size();
        
        // Depth-First Search (DFS) function
        auto dfs = [&](int i, int j, auto&& dfs) -> void {
            if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0) {
                return;
            }
            
            grid2[i][j] = 0;
            dfs(i + 1, j, dfs);
            dfs(i, j + 1, dfs);
            dfs(i, j - 1, dfs);
            dfs(i - 1, j, dfs);
        };
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j] == 1 && grid1[i][j] == 0) {
                    dfs(i, j, dfs);
                }
            }
        }
        
        int c = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j] == 1) {
                    dfs(i, j, dfs);
                    ++c;
                }
            }
        }
        
        return c;
    }
};