<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:
        def measure_island(grid, i, j):
            trav = [(i,j)] # (i, j)
            tiles = set()
            while trav:
                x,y = trav.pop()
                if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
                    continue
                if (x,y) in tiles:
                    continue
                if grid[x][y] == 0:
                    continue
                tiles.add((x,y))
                for (dx,dy) in [(1,0), (-1,0), (0,1), (0,-1)]:
                    trav.append((x+dx, y+dy))
            return tiles


        n_subislands = 0
        seen = set()
        grid1_map = {} # [i,j] -> island number
        grid1_islands = {} # island number -> island coords
        grid1_isles = 0
        for i,row in enumerate(grid2):
            for j,tile in enumerate(row):
                if (i,j) in seen:
                    continue
                if tile != 1:
                    continue
                grid2_island_coords = measure_island(grid2, i,j)
                seen.update(grid2_island_coords)
                grid1_island_coords = None
                if (grid1_islenum := grid1_map.get((i,j))) != None:
                    grid1_island_coords = grid1_islands[grid1_islenum]
                else:
                    grid1_island_coords = measure_island(grid1, i, j)
                    for coords in grid1_island_coords:
                        grid1_map[coords] = grid1_isles
                    grid1_islands[grid1_isles] = grid1_island_coords
                    grid1_isles += 1
                # its a subisland if every cell in grid2_island_coords is in grid1_island_coords
                if all([coord in grid1_island_coords for coord in grid2_island_coords]):
                    n_subislands += 1
        return n_subislands
64230