<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(object):
    def countSubIslands(self, grid1, grid2):
        """
        :type grid1: List[List[int]]
        :type grid2: List[List[int]]
        :rtype: int
        """

        if not grid1:
            return 0

        self.cells_visited = {}
        self.directions = [(1,0), (-1,0), (0,1), (0,-1)]


        def find_island(grid: List[List[int]],
                i: int,
                j: int, 
                grid_rows: int,
                grid_cols: int,
                ones_visited: Dict[Tuple[int, int], int]):

            '''
            This function is to find if a island is formed from a origin
            cell in a matrix. 

            @params

            grid: this the input matrix
            i: this is the origin row index
            j: this is the origin colum index
            grid_rows: this is the number of rows
            grid_colums: this is the number of columns
            ones_visited: this is a  dictionary which hold the tupples of
            cells that have been visited in recursive calls

            @return 

            ones_visited: dictionary of islands in grid2
            '''


            if i < 0 or j >= grid_cols or i >= grid_rows or j < 0:
                return False
            
            if grid[i][j] == 0 or ones_visited.get((i,j), None):
                return False

            self.cells_visited[(i,j)] = 1


            ones_visited[(i,j)] = 1
            
            for direction in self.directions:

                find_island(grid,
                        i+direction[0],
                        j+direction[1], 
                        grid_rows,
                        grid_cols,
                        ones_visited)
            
            return ones_visited

        
        grid2_rows = len(grid2)
        grid2_cols = len(grid2[0])
        grid2_islands = []
        for i in range(0, grid2_rows):
            for j in range(0, grid2_cols):
                ones_visited = {}
                if self.cells_visited.get((i,j), None):
                    continue
   
                if grid1[i][j] == 1:
                    result = find_island(grid2,
                            i,
                            j, 
                            grid2_rows,
                            grid2_cols,
                            ones_visited)
                
                    if result:
                        grid2_islands.append(result)

        subisland_count = 0

        # iterate over each island and check if island cells are island cells
        # in grid1
        for island2 in grid2_islands:

            subisland = True
            # iterate each cell of the island
            for cell in island2:
                i = cell[0]
                j = cell[1]

                # if any cell if found not be an island cell in grid1 then
                # this grid2 island in not a subisland
                if grid1[i][j] != 1:
                    subisland = False

                    break
            # only count if the island is a subisland
            if subisland:
                subisland_count += 1

        return subisland_count



                
                
        
67710