<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 __init__(self) -> None:
        self.directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]
    
    '''
    create 2d array of visited coordinates
    num_subislands = 0
    for each unvisited coordinate
        if coord is land in grid1 and grid2
            bfs to check for subisland at coord, marking visited cells in process
        mark coord as visited
    '''
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        num_subislands = 0
        rows = len(grid1)
        cols = len(grid1[0])
        visited = [[False] * cols for _ in range(rows)]

        for i in range(cols):
            for j in range(rows):
                coord = (i, j)
                if self.is_visited(visited, coord):
                    continue

                is_grid2_land = self.is_land(grid2, coord)

                if is_grid2_land: # Possible subisland
                    num_subislands += self.is_subisland(grid1, grid2, visited, coord)

                self.mark_visited(visited, coord)
        
        return num_subislands
    
    def is_subisland(self, grid1: List[List[int]], grid2: List[List[int]], visited: List[List[bool]], start: tuple) -> int:
        is_subisland = 1
        stack = []
        stack.append(start)
        self.mark_visited(visited, start)

        while stack:
            coord = stack.pop()
            x, y = coord
            is_grid1_land = self.is_land(grid1, coord)
            
            if not is_grid1_land:
                is_subisland = 0

            for direction in self.directions:
                x_direction, y_direction = direction
                neighbor = (x + x_direction, y + y_direction)

                if self.is_valid_coord(grid2, neighbor) and not self.is_visited(visited, neighbor) and self.is_land(grid2, neighbor):
                    stack.append(neighbor)
                    self.mark_visited(visited, neighbor)

        return is_subisland
    
    def is_land(self, grid: List[List[int]], coord: tuple) -> bool:
        x, y = coord
        is_land = grid[y][x] == 1

        return is_land
    
    def is_visited(self, visited: List[List[bool]], coord: tuple) -> bool:
        x, y = coord
        is_visited = visited[y][x]

        return is_visited
    
    def mark_visited(self, visited: List[List[bool]], coord: tuple) -> bool:
        x, y = coord
        visited[y][x] = True
    
    def is_valid_coord(self, grid: List[List[int]], coord: tuple) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        x, y = coord

        is_valid_row = 0 <= x and x < cols
        is_valid_col = 0 <= y and y < rows
        is_valid_coord = is_valid_row and is_valid_col

        return is_valid_coord

2729