C++에서 폐쇄된 섬의 수

0(땅)과 1(물)로 구성된 2D 그리드가 있다고 가정합니다. 섬은 최대 4방향으로 연결된 0의 그룹입니다. 닫힌 섬은 완전히 1로 둘러싸인 섬입니다. 닫힌 섬의 수를 찾아야 합니다. 그리드가 다음과 같다면

따라서 출력은 2가 됩니다. 물로 완전히 둘러싸인 두 개의 섬이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 변수 플래그 정의

• 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로 채웁니다.

• 0 ~ n – 1 범위의 i에 대해

  • 0 ~ m – 1 범위의 j에 대해

    • g[i, j] =0이면

      • 플래그 :=참

      • dfs(g, i, j, n, m)

      • 플래그 :=참

      • ans :=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