<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:

        # do DFS to get the islands from grid2
        # when we find a cell with 1 in grid2, check if grid1 has that corresponding cell as 1 or not
        # if yes that's a valid sub island, increment count, if not it's not valid

        visited = set()
        island_count = 0

        rows = len(grid1)
        cols = len(grid1[0])

        def dfs(r, c):
            # base case: if we go out of bounds or we hit water or we already visited this cell
            if (r < 0 or c < 0) or (r == rows or c == cols) or grid2[r][c] == 0 or (r, c) in visited:
                return True

            visited.add((r,c))
            result = True # to check if island is sub island
            if grid1[r][c] == 0:
                # corresponding land doesn't exist in grid1
                result = False
            
            # running dfs in all 4 directions
            # all we need is one False for the whole thing to return False b/c every 1 in grid2 needs corresponding 1 in grid1
            result = dfs(r + 1, c) and result
            result = dfs(r - 1, c) and result
            result = dfs(r, c + 1) and result
            result = dfs(r, c - 1) and result

            return result


        for r in range(rows):
            for c in range(cols):
                # checking if its a land(1) cell and hasn't been visited yet and if it's and island
                if grid2[r][c] and (r,c) not in visited and dfs(r, c):
                    island_count += 1
        
        return island_count





        
2280