C++ . में विशिष्ट द्वीपों की संख्या

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

एक द्वीप को दूसरे द्वीप के समान माना जाता है जब एक द्वीप का अनुवाद (और घुमाया या प्रतिबिंबित नहीं) दूसरे के बराबर किया जा सकता है।

तो, अगर इनपुट पसंद है

तो आउटपुट 3

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

• फ़ंक्शन dfs() को परिभाषित करें, इसमें x, y, ग्रिड, अस्थायी, c,

  लगेगा

• यदि x और y ग्रिड पंक्तियों और स्तंभों के अंदर नहीं हैं और ग्रिड[x,y] 0 है, तो -

  • वापसी

• ग्रिड [एक्स, वाई] :=0

• अस्थायी :=अस्थायी संयोजन c

• dfs(x + 1, y, ग्रिड, अस्थायी, 'r')

• डीएफएस (एक्स -1, वाई, ग्रिड, अस्थायी, 'एल')

• डीएफएस (एक्स, वाई + 1, ग्रिड, अस्थायी, 'डी')

• dfs(x, y-1, ग्रिड, अस्थायी, 'यू')

• अस्थायी:=अस्थायी 'बी' को जोड़ना

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

• रिट:=0

• देखे गए एक सेट को परिभाषित करें

• इनिशियलाइज़ करने के लिए:=0, जब मैं <ग्रिड की पंक्ति गणना, अद्यतन (i 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • अगर ग्रिड [i, j] शून्य नहीं है, तो -

      • औक्स:=खाली स्ट्रिंग

      • dfs(i, j, grid, aux, 's')

      • यदि ऑक्स का दौरा नहीं किया जाता है, तो -

        • (रिटर्न 1 से बढ़ाएं)

        • विज़िट किए गए में ऑक्स डालें

• वापसी रिट

उदाहरण

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

#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> >& grid, string& temp, char c){
      if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y])
         return;
      grid[x][y] = 0;
      temp += c;
      dfs(x + 1, y, grid, temp, 'r');
      dfs(x - 1, y, grid, temp, 'l');
      dfs(x, y + 1, grid, temp, 'd');
      dfs(x, y - 1, grid, temp, 'u');
      temp += 'b';
   }
   int numDistinctIslands(vector<vector<int>>& grid) {
      int ret = 0;
      set<string> visited;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j]) {
               string aux = "";
               dfs(i, j, grid, aux, 's');
               if (!visited.count(aux)) {
                  ret++;
                  visited.insert(aux);
               }
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v =
   {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
   cout<<(ob.numDistinctIslands(v));
}

इनपुट

{{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}

आउटपुट

3