C++のエンクレーブの数

2D配列Aを指定したとすると、各セルは0（海を表す）または1（陸を表す）になります。ここでの移動は、ある土地の正方形から別の土地の正方形へ、またはグリッドの境界から離れて4方向に歩くことで構成されます。グリッド内の土地の正方形の数を見つける必要があります。この数の移動でグリッドの境界を離れることはできません。したがって、グリッドが-

0で囲まれたものが3つあり、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の場合は、

  を返します。

• set 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の場合

    • 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