सी++ में एन्क्लेव की संख्या

मान लीजिए कि हमने एक 2D सरणी A दी है, अब प्रत्येक सेल 0 (समुद्र का प्रतिनिधित्व करता है) या 1 (भूमि का प्रतिनिधित्व करता है) यहां एक चाल में एक भूमि वर्ग से 4-प्रत्यक्ष रूप से दूसरे भूमि वर्ग तक, या ग्रिड की सीमा से बाहर चलना शामिल है। हमें ग्रिड में भूमि वर्गों की संख्या ज्ञात करनी है जिसके लिए हम किसी भी संख्या में ग्रिड की सीमा से बाहर नहीं जा सकते हैं। तो अगर ग्रिड की तरह है -

उत्तर 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 है, तो वापस लौटें

• सेट ए [एक्स, वाई]:=0

• कश्मीर के लिए 0 से 3 की सीमा में

  • एनएक्स:=डीआईआर [के, 0] + एक्स, एनवाई:=डीआईआर [के, 1] + वाई

  • डीएफएस (एनएक्स, एनवाई, ए)

• मुख्य विधि से निम्न कार्य करें

• ret :=0, n :=A की पंक्ति गणना

• m :=A की कॉलम संख्या यदि n 0 नहीं है, अन्यथा m :=0

• मेरे लिए 0 से n - 1 की सीमा में

  • अगर A[i, 0] =1, तो dfs(i, 0, A) पर कॉल करें

  • अगर A[i, m-1] 1 है, तो dfs(i, m-1, A) पर कॉल करें

• मेरे लिए 0 से मी - 1 की सीमा में

  • अगर A[0, i] =1, तो dfs(0, i, A) पर कॉल करें

  • अगर A[n-1, i] 1 है, तो dfs(n-1, i, A) पर कॉल करें

• मेरे लिए 0 से n - 1 की सीमा में

  • j के लिए 0 से m - 1 की सीमा में

    • रिट:=रिट + ए[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