C++ . में बंद द्वीपों की संख्या

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

तो आउटपुट 2 होगा। दो द्वीप हैं, जो पूरी तरह से पानी से घिरे हुए हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक परिवर्तनशील ध्वज परिभाषित करें

• डीएफएस नामक एक विधि को परिभाषित करें, यह ग्रिड लेगा, i, j, n और m

• यदि i और j ग्रिड की सीमा के अंदर नहीं हैं, तो ध्वज सेट करें:=झूठा और वापस लौटें

• अगर 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, मैं, जे-1, एन, एम)

• मुख्य विधि इस प्रकार होगी -

• क्रम n x m का dp मैट्रिक्स बनाएं, और इसे -1 से भरें

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

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

    • अगर g[i, j] =0, तो

      • झंडा :=सच

      • डीएफएस (जी, आई, जे, एन, एम)

      • झंडा :=सच

      • उत्तर:=उत्तर + झंडा

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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