假设我们给定了一个2D数组A，现在每个像元是0（代表海洋）或1（代表陆地）。这里的移动包括从一个陆地正方形4向走到另一个陆地正方形，或者离开网格边界。我们必须找到网格中不能以任何数量的步距走出网格边界的土地广场的数量。所以如果网格像-
0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
0 | 1个 | 1 | 0 |
0 | 0 | 0 | 0 |
答案将是3，因为三个数字都用0括起来，而一个1则没有括起来。
为了解决这个问题，我们将遵循以下步骤-
制作方向数组目录，并存储[[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
对于0到3范围内的k
nx：= dir [k，0] + x，ny：= dir [k，1] + y
dfs(nx,ny,A)
从主要方法执行以下操作
ret：= 0，n：= A的行数
m：=如果n不为0的A的列计数，否则m：= 0
对于i，范围为0至n – 1
如果A [i，0] = 1，则调用dfs(i,0,A)
如果A [i，m – 1]为1，则调用dfs（i，m – 1，A）
当我的范围是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
ret：= ret + A [i，j]
对于j，范围从0到m – 1
返回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