C++での閉鎖された島の数

0（土地として）と1（水として）で構成される2Dグリッドがあるとします。島は、最大4方向に接続された0のグループです。閉じた島は、完全に1で囲まれた島です。閉じた島の数を見つける必要があります。したがって、グリッドが次のような場合

したがって、出力は2になります。完全に水に囲まれた2つの島があります。

これを解決するには、次の手順に従います-

• 変数フラグを定義する

• dfsと呼ばれるメソッドを定義します。これにより、グリッドi、j、n、およびmが取得されます

  。
• iとjがグリッドの範囲内にない場合は、フラグ：=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）

• 主な方法は次のようになります-

• 次数nxmのdp行列を作成し、-1で埋めます

• 0からn–1の範囲のiの場合

  • 0からm–1の範囲のjの場合

    • g [i、j] =0の場合、

      • フラグ：=true

      • dfs（g、i、j、n、m）

      • フラグ：=true

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