<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:
        
        # I have m * n matrix with 0s and 1s. 1s represent the land.
        # Movement can be in only 4 directions
        # We need to find islands in grid2, such that the islands are sub-island of the grid2
        
        
        # I can use DFS, because it can be implemented easily using stack
        m = len(grid1)
        
        if m == 0:
            return 0
        
        n = len(grid1[0])
        
        num_islands = 0
        st = list()
        
        for row in range(m):
            for col in range(n):
                if grid2[row][col] == 1 and grid1[row][col] == 1:
                    
                    counts = self.mark_as_part_of_island(row, col, m, n, grid1, grid2)
                    print(row, col, counts)
                    if counts[0] == counts[1]:
                        num_islands += 1
                    
        return num_islands
                    
                
    def add_tuples(self, val1, val2) -> None:
        return (val1[0] + val2[0], val1[1] + val2[1])
                
    def mark_as_part_of_island(self, row: int, col: int, m: int, n: int, grid1, grid2):
        '''
            This returns tuple of count of islands overlapping and without overlapping
        
        '''
        # print(row, col, 'mark_as_part_of_island')
        
        if row < 0 or col < 0 or row == m or col == n or grid2[row][col] != 1:
            return (0, 0)
        
        current_counts = (1 if grid1[row][col] == 1 else 0, 1)
        grid2[row][col] = -1
        
        adjacents = [
            (-1, 0),
            (1, 0),
            (0, -1),
            (0, 1)
        ]


        for path in adjacents:
            current_counts = self.add_tuples(current_counts, self.mark_as_part_of_island(row + path[0], col + path[1], m, n, grid1, grid2))
            
        return current_counts

2460