<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:
        
        adj = [[0,1],[1,0],[0,-1],[-1,0]]
        
        def rec(src,visited,grid,curr, pastVisited=None):
            
            q = deque([src])
            visited[src]=curr
            past = set()
            pastNotFound = False 
            while(q):
                x,y = q.popleft()
                if pastVisited:
                    if (x,y) not in pastVisited:
                        pastNotFound = True
                    else:
                        past.add(pastVisited[(x,y)])
                
                for adjx,adjy in adj:
                    i,j = x+adjx,y+adjy
                    if i<0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j]==0 or (i,j) in visited:
                        continue
                    
                    
                    visited[(i,j)]=curr
                    q.append((i,j))
            
            
            
            if pastVisited and (pastNotFound or len(past) > 1):
                return False
            return True
            
        
        
        curr = 501
        visited1,visited2 = {},{}
        
        for i in range(len(grid1)):
            for j in range(len(grid1[0])):
                if (i,j) == (25,0):
                    print(grid1[i][j], (25,0) not in visited1)
                if grid1[i][j] == 1 and (i,j) not in visited1:
                    rec((i,j),visited1,grid1,curr)
                    print(i,j)
                    curr+=1
        
        print((25,0) in visited1)
        print("----")
        ans = 0
        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] == 1 and (i,j) not in visited2:
                    
                    if rec((i,j),visited2,grid2,curr,visited1):
                        ans += 1
                    # print(i,j,ans)
                    
                        
                    
                    curr+=1
        
        return ans
        
                    
                    
                    
                    
                    
                    
            
64810