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

typedef unsigned long Coordinate;

class Solution {
public:
    inline unsigned short get_row(Coordinate coord)
    {
        return static_cast<unsigned short>((coord & 0xffff0000) >> sizeof(unsigned short) * 8);
    }

    inline unsigned short get_col(Coordinate coord)
    {
        return static_cast<unsigned short>((coord & 0xffff));
    }

    inline Coordinate get_coord(unsigned short row, unsigned short col)
    {
        Coordinate coord = row;
        coord <<= sizeof(unsigned short) * 8;
        coord |= col;
        return coord;
    }

    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        unordered_set<Coordinate> explored_cells;
        queue<Coordinate> adjacent_cells;
        int island_count = 0;
        unsigned short total_rows = grid1.size();
        unsigned short total_cols = grid1[0].size();

        // Explore each cell in both grids
        for(unsigned short row_index = 0; row_index < total_rows; ++row_index)
        {
            for(unsigned short col_index = 0; col_index < total_cols; ++col_index)
            {
                // Check to see if cell is valid on both grids, DFS on adjacent cells
                if(grid2[row_index][col_index] &&
                   !explored_cells.count(get_coord(row_index, col_index)))
                {
                    bool contained = grid1[row_index][col_index];  
                    explored_cells.insert(get_coord(row_index, col_index));

                    if(row_index + 1 < total_rows)
                    {
                        adjacent_cells.push(get_coord(row_index + 1, col_index));
                    }
                    if(col_index + 1 < total_cols)
                    {
                        adjacent_cells.push(get_coord(row_index, col_index + 1));
                    }

                    while(!adjacent_cells.empty())
                    { 
                        Coordinate explore_coord = adjacent_cells.front();
                        unsigned short explore_row = get_row(explore_coord);
                        unsigned short explore_col = get_col(explore_coord);

                        adjacent_cells.pop();

                        if(grid2[explore_row][explore_col] &&
                           !explored_cells.count(get_coord(explore_row, explore_col)))
                        {
                            // Ensure island in grid2 is completely contained in grid1
                            contained &= grid1[explore_row][explore_col];
                            explored_cells.insert(get_coord(explore_row, explore_col));

                            if(explore_row - 1 >= 0)
                            {
                                adjacent_cells.push(get_coord(explore_row - 1, explore_col));
                            }
                            if(explore_col - 1  >= 0)
                            {
                                adjacent_cells.push(get_coord(explore_row, explore_col - 1));
                            }
                            if(explore_row + 1 < total_rows)
                            {
                                adjacent_cells.push(get_coord(explore_row + 1, explore_col));
                            }
                            if(explore_col + 1 < total_cols)
                            {
                                adjacent_cells.push(get_coord(explore_row, explore_col + 1));
                            }
                        }
                    }

                    island_count += contained;
                }
            }
        }

        return island_count;
    }
};
156357