C++ এ স্বতন্ত্র দ্বীপের সংখ্যা

ধরুন আমাদের একটি বাইনারি 2D অ্যারে গ্রিড আছে, এখানে একটি দ্বীপ হল 1 এর (ভূমি) একটি গ্রুপ যা 4- দিকনির্দেশকভাবে (অনুভূমিক বা উল্লম্ব।) সংযুক্ত। আমরা গ্রিডের চারটি প্রান্তই পানি দ্বারা বেষ্টিত বলে ধরে নিতে পারি। আমাদের স্বতন্ত্র দ্বীপের সংখ্যা গণনা করতে হবে।

একটি দ্বীপকে অন্য দ্বীপের সমান বলে মনে করা হয় যখন একটি দ্বীপ অন্যটির সমান করার জন্য অনুবাদ করা যায় (এবং ঘোরানো বা প্রতিফলিত করা হয় না)।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 3

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি x, y, গ্রিড, temp, c,

  লাগবে

• যদি x এবং y গ্রিডের সারি এবং কলামের ভিতরে না থাকে এবং গ্রিড[x,y] 0 হয়, তাহলে −

  • ফেরত

• গ্রিড[x, y] :=0

• temp :=temp concatenate c

• dfs(x + 1, y, গ্রিড, টেম্প, 'r')

• dfs(x - 1, y, গ্রিড, temp, 'l')

• dfs(x, y + 1, grid, temp, 'd')

• dfs(x, y - 1, grid, temp, 'u')

• temp :=temp concatenate 'b'

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ret :=0

• পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i <গ্রিডের সারি গণনা, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • j আরম্ভ করার জন্য :=0, যখন j

    • যদি গ্রিড[i, j] অ-শূন্য হয়, তাহলে -

      • aux :=খালি স্ট্রিং

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

      • যদি aux পরিদর্শন না হয়, তাহলে -

        • (রেট 1 দ্বারা বৃদ্ধি করুন)

        • ভিজিটেড

          এ aux ঢোকান

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#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