<p>You are given two <code>m x n</code> binary matrices <code>grid1</code> and <code>grid2</code> containing only <code>0</code>&#39;s (representing water) and <code>1</code>&#39;s (representing land). An <strong>island</strong> is a group of <code>1</code>&#39;s connected <strong>4-directionally</strong> (horizontal or vertical). Any cells outside of the grid are considered water cells.</p>

<p>An island in <code>grid2</code> is considered a <strong>sub-island </strong>if there is an island in <code>grid1</code> that contains <strong>all</strong> the cells that make up <strong>this</strong> island in <code>grid2</code>.</p>

<p>Return the <em><strong>number</strong> of islands in </em><code>grid2</code> <em>that are considered <strong>sub-islands</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/test1.png" style="width: 493px; height: 205px;" />
<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/03/testcasex2.png" style="width: 491px; height: 201px;" />
<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 2 
<strong>Explanation: </strong>In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid1.length == grid2.length</code></li>
	<li><code>n == grid1[i].length == grid2[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>grid1[i][j]</code> and <code>grid2[i][j]</code> are either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:

        '''
        idea:
        go through all cells in grid2, if it is an island cell and grid1 is also an island cell, then keep it marked as
        '1'. If grid 1 has an ocean cell, then change the '1' to a '0'. Go through the grid again, perform dfs to count
        the amount of islands
        '''

        # total_rows = len(grid2)
        # total_cols = len(grid2[0])

        # # change grid2 to only have 'valid' sub-island cells
        # for row in range(total_rows):
        #     for col in range(total_cols):
        #         if grid2[row][col] and not grid1[row][col]: 
        #             grid2[row][col] = 0
        
        # # dfs for counting islands
        # visited = set()
        # def dfs(r, c):

        #     if r not in range(total_rows) or c not in range(total_cols) or not grid2[r][c] or (r,c) in visited:
        #         return 
            
        #     visited.add((r,c))
            
        #     dfs(r+1, c) 
        #     dfs(r-1, c) 
        #     dfs(r, c+1) 
        #     dfs(r, c-1)

        #     return 
        
        # # count the number of valid islands
        # islands = 0
        # for row in range(total_rows):
        #     for col in range(total_cols):
        #         if grid2[row][col]:
        #             if (row, col) not in visited:
        #                 dfs(row, col)
        #                 islands += 1
        # return islands

        '''
        for every valid cell in grid2, perform bfs on the cell - if it is not a '1' in grid1, then mark all the cells 
        as invalid
        if for all the bfs cells there is a 1, then we can count it as an island
        '''
        total_rows = len(grid2)
        total_cols = len(grid2[0])
        islands = 0
        visited = set()
        for row in range(total_rows):
            for col in range(total_cols):
                if grid2[row][col] and (row, col) not in visited:
                    # bfs
                    valid_subisland = True
                    q = deque()
                    q.append((row, col))
                    visited.add((row, col))
                    while q:
                        cellx, celly = q.popleft()
                        if not grid1[cellx][celly]:
                            valid_subisland = False
                        directions = [[0,1],[0,-1],[1,0],[-1,0]]
                        for direction in directions:
                            dx = cellx + direction[0]
                            dy = celly + direction[1]
                            if (
                                dx in range(total_rows) and 
                                dy in range(total_cols) and 
                                grid2[dx][dy] and 
                                (dx, dy) not in visited
                                ):
                                q.append((dx,dy))
                                visited.add((dx,dy))
                    islands += 1 if valid_subisland else 0
        return islands
        
2669