下周开学不能再废了
题目:
1905. Count Sub Islands
给两个二元的二维矩阵a,b其中1代表的是存在的岛屿，求b完全包含于a的岛屿的数目
思路:
本来想说可以用union find然后求出两个矩阵的岛屿再遍历岛屿比较，但想了下保底
复杂度会要跑10**8次肯定不是答案，看了下提示后应该是要用b的岛屿去找，在比较过程
中找过的要修改成0避免重复寻找
bool easycheck(int i,int j,vector<vector<int>>& grid1, vector<vector<int>>&
grid2){
bool tar=true;
grid2[i][j] = 0;
if(grid1[i][j]==0){
tar=false;
}
if(i>0 &&grid2[i-1][j]){
tar&=easycheck(i-1,j,grid1,grid2);
}
if(i<grid2.size()-1 && grid2[i+1][j]){
tar&=easycheck(i+1,j,grid1,grid2);
}
if(j>0 && grid2[i][j-1]){
tar&=easycheck(i,j-1,grid1,grid2);
}
if(j<grid2[0].size()-1&& grid2[i][j+1]){
tar&=easycheck(i,j+1,grid1,grid2);
}
return tar;
}
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>&
grid2) {
int m=grid1.size();
int n=grid1[0].size();
int ans=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(grid2[i][j]){
if(easycheck(i,j,grid1,grid2)){
++ans;
}
}
}
}
return ans;
}