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

def cellNeighbors(source):
    return [
        (source[0], source[1] - 1),
        (source[0], source[1] + 1),
        (source[0] - 1, source[1]),
        (source[0] + 1, source[1]),
    ]

# returns a list of sets, each set contains the indices of cells belonging to the same island
def findIslands(grid):
    frontier = set([(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 1])
    islands = []

    while len(frontier) > 0:
        islands.append(set())
        newIsland = [frontier.pop()]
        while len(newIsland) > 0:
            source = newIsland.pop()
            islands[-1].add(source)

            # Add neighbors of source to newIsland
            for n in cellNeighbors(source):
                if n in frontier:
                    frontier.remove(n)
                    newIsland.append(n)
    return islands

# Floodfill from source, removing filled cells from frontier
# Returns True if all visited cells have value 1 in grid1, False otherwise        
def exploreIsland(frontier, grid1, source):
    island = [source]
    isSubIsland = True
    while len(island) > 0:
        s = island.pop()
        if grid1[s[0]][s[1]] == 0:
            isSubIsland = False
        for n in cellNeighbors(s):
            if n in frontier:
                frontier.remove(n)
                island.append(n)
                
    return isSubIsland

def isSubisland(i, islands):
    for island in islands:
        if island >= i:
            return True
    return False

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        frontier = set([(i, j) for i in range(len(grid2)) for j in range(len(grid2[0])) if grid2[i][j] == 1])
        result = 0
        while len(frontier) > 0:
            if (exploreIsland(frontier, grid1, frontier.pop())):
                result += 1
        return result
        
2161