数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的封闭岛屿数量
假设我们有一个由 0（作为陆地）和 1（作为水）组成的二维网格。岛屿是由 0 组成的最大 4 向连接组。封闭岛屿是被 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。有两个岛屿，完全被水包围。
为了解决这个问题，我们将遵循以下步骤 -
定义一个变量 flag
定义一个名为 dfs 的方法，它将获取网格、i、j、n 和 m
- 如果 i 和 j 不在网格范围内，则设置 flag := 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)
主方法将如下所示 -
创建一个 n x m 阶的 dp 矩阵，并将其填充为 -1
对于 i 的范围从 0 到 n – 1
对于 j 的范围从 0 到 m – 1
如果 g[i, j] = 0，则
flag := true
dfs(g, i, j, n, m)
flag := true
ans := ans + flag
返回 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
更新于: 2020 年 5 月 2 日
233 次查看
广告