这道题咋一看很难,但是可以转换,将所有靠近边界的非封闭岛屿都变成海洋后,那么剩下的岛屿就是封闭岛屿,最后的问题其实就是求解连通分量个数
class Solution {
private:void closedIsland(vector<vector<int>>& grid,int x,int y){if(x<0||y<0||x>=grid.size()||y>=grid[0].size())return;else if(grid[x][y]==1)return;else{grid[x][y]=1;closedIsland(grid,x,y+1);closedIsland(grid,x+1,y);closedIsland(grid,x,y-1);closedIsland(grid,x-1,y);}}
public:int closedIsland(vector<vector<int>>& grid) {int result=0;int m=grid.size();int n=grid[0].size();//将靠近上边界和下边界的非封闭岛变成海洋for(int i=0;i<n;i++){closedIsland(grid,0,i);closedIsland(grid,m-1,i);}//将左边界和右边界的非封闭岛变成海洋for(int i=0;i<m;i++){closedIsland(grid,i,0);closedIsland(grid,i,n-1);}//由此问题转化为求岛屿的数目for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(grid[i][j]==0){result++;closedIsland(grid,i,j);}return result;}
};