C ++中封闭岛的数量

假设我们有一个2D网格，它由0（作为陆地）和1（作为水）组成。孤岛是最大4方向连接的0s组。封闭的岛屿是完全由1包围的岛屿。我们必须找到封闭岛屿的数量。所以如果网格像

因此输出为2。有两个岛，它们完全被水包围。

为了解决这个问题，我们将遵循以下步骤-

• 定义变量标志

• 定义一个称为dfs的方法，它将采用网格i，j，n和m

• 如果i和j不在网格范围内，则设置标志：= false并返回

• 如果g [i，j] = 1或g [i，j] = -1，则返回

• 如果g [i，j] = 0，则g [i，j] = -1

• 呼叫dfs（g，i + 1，j，n，m），dfs（g，i，j + 1，n，m），dfs(g,i-1,j,n,m)，dfs（g， i，j-1，n，m）

• 主要方法将是-

• 创建一个nxm阶的dp矩阵，并用-1填充

• 对于i，范围为0至n – 1

• 如果g [i，j] = 0，则

• 标志：= true

• dfs(g,i,j,n,m)

• 标志：= true

• ans：= ans +标志

• 对于j，范围从0到m – 1

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector < vector <int> > dp;
   bool flag;
   void dfs(vector<vector<int>>& g, int i, int j, int n, int m){
      if(i>=n || j >=m || i<0 || j<0){
         flag = false;
         return ;
      }
      if(g[i][j] == 1 || g[i][j] == -1)return;
      if(g[i][j] == 0)g[i][j] = -1;
      dfs(g, i+1, j, n, m);
      dfs(g, i, j+1, n, m);
      dfs(g, i-1, j, n, m);
      dfs(g,i, j-1, n, m);
   }
   int closedIsland(vector<vector<int>>& g) {
      int ans = 0;
      int n = g.size();
      int m = g[0].size();
      dp = vector < vector <int> > (n, vector <int> (m, -1));
      for(int i = 0; i < n ; i++){
         for(int j = 0; j < m; j++){
            if(g[i][j] == 0){
               flag = true;
               dfs(g, i , j ,n ,m);
               ans += flag;
            }
         }
      }
   return ans;
   }
};
main(){
   vector<vector<int>> v =
   {{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0
   ,1},{1,1,1,1,1,1,1,0}};
   Solution ob;
   cout << (ob.closedIsland(v));
}

输入值

[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

输出结果

2