数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的飞地数量
假设我们给定一个二维数组 A，现在每个单元格都是 0（表示海洋）或 1（表示陆地）。这里一次移动包括从一个陆地方格 4 个方向地走到另一个陆地方格，或者走到网格的边界外。我们需要找到网格中陆地方格的数量，对于这些陆地方格，我们无法在任意次数的移动中走到网格的边界外。所以如果网格是这样的 -
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
答案将是 3，因为有三个 1 被 0 包围，而一个 1 没有被包围。
为了解决这个问题，我们将遵循以下步骤 -
创建一个方向数组 dir，并存储 [[1,0], [-1,0], [0,1], [0,-1]]
创建一个名为 dfs() 的方法，它将接收 x、y 和矩阵 A
如果 x < 0 或 y > 0 或 x > A 的行数或 y > A 的列数，或者 A[x, y] 为 0，则返回
设置 A[x, y] := 0
对于 k 的范围从 0 到 3
nx := dir[k, 0] + x，ny := dir[k, 1] + y
dfs(nx, ny, A)
从主方法执行以下操作
ret := 0，n := A 的行数
m := A 的列数，如果 n 不为 0，否则 m := 0
对于 i 的范围从 0 到 n – 1
如果 A[i, 0] = 1，则调用 dfs(i, 0, A)
如果 A[i, m – 1] 为 1，则调用 dfs(i, m – 1, A)
对于 i 的范围从 0 到 m – 1
如果 A[0, i] = 1，则调用 dfs(0, i, A)
如果 A[n – 1, i] 为 1，则调用 dfs(n – 1, i, A)
对于 i 的范围从 0 到 n – 1
对于 j 的范围从 0 到 m – 1
ret := ret + A[i, j]
返回 ret
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
void dfs(int x, int y, vector < vector <int>>& A){
if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() ||
A[x][y] == 0) return;
A[x][y] = 0;
for(int k = 0; k < 4; k++){
int nx = dir[k][0] + x;
int ny = dir[k][1] + y;
dfs(nx, ny, A);
}
}
int numEnclaves(vector<vector<int>>& A) {
int ret = 0;
int n = A.size();
int m = n ? A[0].size() : 0;
for(int i = 0; i < n; i++){
if(A[i][0] == 1){
dfs(i, 0, A);
}
if(A[i][m - 1] == 1){
dfs(i, m - 1, A);
}
}
for(int i = 0; i < m; i++){
if(A[0][i] == 1){
dfs(0, i, A);
}
if(A[n - 1][i] == 1){
dfs(n - 1, i, A);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
ret += A[i][j];
}
}
return ret;
}
};
main(){
vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
Solution ob;
cout << (ob.numEnclaves(v1));
}输入
[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出
3
更新于: 2020-04-30
164 次查看
广告