<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 {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int rowCount = grid1.size();
        int colCount = grid1[0].size();
        vector<int> parents = vector<int>(501 * 501);
        // iota(parents.begin(), parents.end(), 0);
        // for (int i = parents.size() - 1; i >= 0; i--)
        //     parents[i] = i;
        static vector<char> sub = vector<char>(501 * 501);
        
        int loc = 0;
        for (int r = 0; r < rowCount; r++) {
            for (int c = 0; c < colCount; c++) {
                if (grid2[r][c] == 0) 
                    parents[loc] = -1;
                else {
                    parents[loc] = loc;
                    sub[loc] = grid1[r][c];
                    if (r > 0 && grid2[r - 1][c]) {
                        int parLoc = find(&parents, loc);
                        int parUp = find(&parents, loc - colCount);
                        if (parLoc != parUp) {
                            parents[parUp] = parLoc;
                            sub[parUp] = sub[parLoc] = (sub[parUp] & sub[parLoc]);
                        }
                    }
                    if (c > 0 && grid2[r][c - 1]) {
                        int parLoc = find(&parents, loc);
                        int parLeft = find(&parents, loc - 1);
                        if (parLoc != parLeft) {
                            parents[parLeft] = parLoc;
                            sub[parLeft] = sub[parLoc] = (sub[parLeft] & sub[parLoc]);
                        }
                    }
                }
                loc++;
            }
        }

        int result = 0;
        for (loc = parents.size() - 1; loc >= 0; loc--)
            if (parents[loc] == loc) 
                result += sub[loc];
        return result;
    }

    
private:
    int find(vector<int>* parents, int loc) {
        if ((*parents)[loc] == loc)  return loc;
        return (*parents)[loc] = find(parents, (*parents)[loc]);
    }
};



//---------------------------------------------------------------------------------
// class Solution {
// public:
//     int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
//         int rowCount = grid1.size();
//         int colCount = grid1[0].size();
//         vector<int> parents(rowCount * colCount);
//         iota(parents.begin(), parents.end(), 0);
//         // for (int i = parents.size() - 1; i >= 0; i--)
//         //     parents[i] = i;
//         vector<char> sub(rowCount * colCount);
        
//         int loc = 0;
//         for (int r = 0; r < rowCount; r++) {
//             for (int c = 0; c < colCount; c++) {
//                 if (grid2[r][c] == 0) 
//                     parents[loc] = -1;
//                 else {
//                     sub[loc] = grid1[r][c];
//                     if (r > 0 && grid2[r - 1][c]) {
//                         int parLoc = find(&parents, loc);
//                         int parUp = find(&parents, loc - colCount);
//                         if (parLoc != parUp) {
//                             parents[parUp] = parLoc;
//                             sub[parUp] = sub[parLoc] = (sub[parUp] & sub[parLoc]);
//                         }
//                     }
//                     if (c > 0 && grid2[r][c - 1]) {
//                         int parLoc = find(&parents, loc);
//                         int parLeft = find(&parents, loc - 1);
//                         if (parLoc != parLeft) {
//                             parents[parLeft] = parLoc;
//                             sub[parLeft] = sub[parLoc] = (sub[parLeft] & sub[parLoc]);
//                         }
//                     }
//                 }
//                 loc++;
//             }
//         }

//         int result = 0;
//         for (loc = parents.size() - 1; loc >= 0; loc--)
//             if (parents[loc] == loc) 
//                 result += sub[loc];
//         return result;
//     }

    
// private:
//     int find(vector<int>* parents, int loc) {
//         if ((*parents)[loc] == loc)  return loc;
//         return (*parents)[loc] = find(parents, (*parents)[loc]);
//     }
// };



//---------------------------------------------------------------------------------
// class Solution {
// public:
//     int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
//         int rowCount = grid1.size();
//         int colCount = grid1[0].size();
//         vector<int> parents(rowCount * colCount);
//         iota(parents.begin(), parents.end(), 0);
//         // for (int i = parents.size() - 1; i >= 0; i--)
//         //     parents[i] = i;
        
//         int loc = 0;
//         for (int r = 0; r < rowCount; r++) {
//             for (int c = 0; c < colCount; c++) {
//                 // cout << r << "  " << c << "  " << loc << endl;
//                 if (grid2[r][c] == 0) 
//                     parents[loc] = -1;
//                 else {
//                     if (r > 0 && grid2[r - 1][c]) {
//                         int parLoc = find(&parents, loc);
//                         int parUp = find(&parents, loc - colCount);
//                         if (parLoc != parUp) {
//                             parents[parUp] = parLoc;
//                             int parUpRow = parUp / colCount;
//                             int parUpCol = parUp % colCount;
//                             grid1[r][c] = grid1[parUpRow][parUpCol] = (grid1[r][c] & grid1[parUpRow][parUpCol]);
//                             // cout << "  join up: " << grid1[r][c] << endl;
//                         }
//                     }
//                     if (c > 0 && grid2[r][c - 1]) {
//                         int parLoc = find(&parents, loc);
//                         int parLeft = find(&parents, loc - 1);
//                         if (parLoc != parLeft) {
//                             parents[parLeft] = parLoc;
//                             int parLeftRow = parLeft / colCount;
//                             int parLeftCol = parLeft % colCount;
//                             grid1[r][c] = grid1[parLeftRow][parLeftCol] = (grid1[r][c] & grid1[parLeftRow][parLeftCol]);
//                             // cout << "  join left: " << grid1[r][c] << endl;
//                         }
//                     }
//                 }
//                 loc++;
//             }
//         }

//         int result = 0;
//         loc = 0;
//         for (int r = 0; r < rowCount; r++) {
//             for (int c = 0; c < colCount; c++) {
//                 if (parents[loc] == loc++) {
//                     result += grid1[r][c];
//                     // cout << "root at  " << r << "  " << c << "  " << grid1[r][c] << endl;
//                 }
//                 // cout << parents[loc-1] << ":" << grid1[r][c] << " ";
//             }
//             // cout << endl;
//         }
//         return result;
//     }

    
// private:
//     int find(vector<int>* parents, int loc) {
//         if ((*parents)[loc] == loc)  return loc;
//         return (*parents)[loc] = find(parents, (*parents)[loc]);
//     }
// };



//---------------------------------------------------------------------------------
// class Solution {
// public:
//     // Solution() {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }

//     int rowLim = 0;
//     int colLim = 0;

//     int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
//         rowLim = grid1.size() - 1;
//         colLim = grid1[0].size() - 1;
        
//         // Find islands in grid2[][].  Check if all land in a grid2[][] 
//         // island has land in the corresponding grid1[][] cell.
//         int subIslandCount = 0;
//         for (int r = rowLim; r >= 0; r--) {
//             vector<int>& row = grid2[r];
//             for (int c = colLim; c >= 0; c--) 
//                 if (row[c] == 1) 
//                     subIslandCount += checkSubIsland(r, c, grid1, grid2);
//         }
//         return subIslandCount;
//     }
    

// private:
//     // Recursively check a grid2[][] island to see if it is a subIsland.
//     // Return:  0==>Not a sub island.    1==>Is a sub island.
//     int checkSubIsland(int r, int c, vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
//         grid2[r][c] = -1;
//         int isSubIsland = grid1[r][c];
//         if (r > 0 && grid2[r - 1][c] == 1)      isSubIsland &= checkSubIsland(r - 1, c, grid1, grid2);
//         if (r < rowLim && grid2[r + 1][c] == 1) isSubIsland &= checkSubIsland(r + 1, c, grid1, grid2);
//         if (c > 0 && grid2[r][c - 1] == 1)      isSubIsland &= checkSubIsland(r, c - 1, grid1, grid2);
//         if (c < colLim && grid2[r][c + 1] == 1) isSubIsland &= checkSubIsland(r, c + 1, grid1, grid2);
//         return isSubIsland;
//     }
// };
150747