假设我们有一个2D网格,它由0(作为陆地)和1(作为水)组成。孤岛是最大4方向连接的0s组。封闭的岛屿是完全由1包围的岛屿。我们必须找到封闭岛屿的数量。所以如果网格像
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。有两个岛,它们完全被水包围。
为了解决这个问题,我们将遵循以下步骤-
定义变量标志
定义一个称为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