2D 배열 A가 주어졌다고 가정하고 이제 각 셀은 0(바다를 나타냄) 또는 1(땅을 나타냄)입니다. 여기에서 이동은 한 육지 광장에서 다른 육지 광장으로 4-방향으로 걷는 것으로 구성되거나 그리드의 경계에서 벗어납니다. 우리는 그리드의 경계에서 이동할 수 없는 그리드의 사각형 수를 찾아야 합니다. 따라서 그리드가 다음과 같은 경우 -
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
0으로 묶인 3개와 1로 묶이지 않은 1개가 있으므로 답은 3입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
방향 배열 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
-
범위 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
-
0 ~ n – 1 범위의 i에 대해
-
A[i, 0] =1이면 dfs(i, 0, A)
를 호출합니다. -
A[i, m – 1]이 1이면 dfs(i, m – 1, A)
를 호출합니다.
-
-
0 ~ m – 1 범위의 i에 대해
-
A[0, i] =1이면 dfs(0, i, A)
를 호출합니다. -
A[n – 1, i]가 1이면 dfs(n – 1, i, A)
를 호출합니다.
-
-
0 ~ n – 1 범위의 i에 대해
-
0 ~ m – 1 범위의 j에 대해
-
렛 :=렛 + A[i,j]
-
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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