C ++中封闭岛的数量

2023-11-16 09:19:35

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

11111110
10000110
10101110
10000101
11111110

因此输出为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
    • 作者:
    • 原文链接:
      更新时间:2023-11-16 09:19:35