# Leetcode 1020. Number of Enclaves

--

You are given two `m x n` binary matrices `grid1` and `grid2` containing only `0`'s (representing water) and `1`'s (representing land). An island is a group of `1`'s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in `grid2` is considered a sub-island if there is an island in `grid1` that contains all the cells that make up this island in `grid2`.

Return the number of islands in `grid2` that are considered sub-islands.

Example 1:

`Input: 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]]Output: 3Explanation: 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.`

Example 2:

`Input: 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]]Output: 2 Explanation: 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.`

Solution:

`class Solution {public:    int rsize{0};    int csize{0};    int count{0};    vector<vector<int>> next{{1,0}, {-1,0}, {0,1}, {0,-1}};        int dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, vector<vector<bool>>& visited, int r, int c, bool& sea) {        if (r == rsize || r < 0 || c == csize || c < 0 || visited[r][c] || grid2[r][c] == 0) {            return 0;        }                     if (grid1[r][c] == 0) {            sea = true;        }visited[r][c] = true;        for (int i=0; i<4; i++) {            dfs(grid1, grid2, visited, r+next[i][0], c+next[i][1], sea);        }        if (sea)            return 0;                return 1;         }        int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {        rsize = grid1.size();        csize = grid1[0].size();                 vector<vector<bool>> visited(rsize, vector<bool>(csize, false));        for (int i=0; i<rsize; i++) {            for (int j=0; j<csize; j++) {                if (grid1[i][j]) {                    bool sea = false;                    count += dfs(grid1, grid2, visited, i, j, sea);                }            }        }        return count;                  }};`

Runtime: 393 ms, faster than 77.23% of C++ online submissions for Count Sub Islands.

Memory Usage: 90.3 MB, less than 63.61% of C++ online submissions for Count Sub Islands.