資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告