C++ এ কমিউনিকেশন টাওয়ারে ন্যূনতম সংখ্যক গ্রুপ খুঁজে বের করার প্রোগ্রাম?

ধরুন আমাদের একটি 2D বাইনারি ম্যাট্রিক্স আছে যেখানে 1 একটি কমিউনিকেশন টাওয়ারকে প্রতিনিধিত্ব করে এবং 0 একটি খালি সেলকে প্রতিনিধিত্ব করে। টাওয়ারগুলি নিম্নলিখিত উপায়ে যোগাযোগ করতে পারে:1. যদি টাওয়ার A, এবং B টাওয়ার একই সারি বা কলামে থাকে তবে তারা একে অপরের সাথে যোগাযোগ করতে পারে। 2. যদি টাওয়ার A টাওয়ার B এর সাথে কথা বলতে পারে এবং B C এর সাথে কথা বলতে পারে, তাহলে A C এর সাথে কথা বলতে পারে (ট্রানজিটিভ সম্পত্তি)। আমাদের সেখানে মোট টাওয়ার গ্রুপের সংখ্যা খুঁজে বের করতে হবে (এখানে একটি গ্রুপ টাওয়ারের একটি তালিকা যা একে অপরের সাথে কথা বলতে পারে)।

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

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি একটি 2D অ্যারে ম্যাট্রিক্স, i, j, n, m,

• ম্যাট্রিক্স[i, j] :=2

• আরম্ভ করার জন্য k :=1, যখন k

  • p :=(i + k) mod n

  • q :=j

  • যদি ম্যাট্রিক্স[p, q] 1 এর মত হয়, তাহলে:

    • dfs(ম্যাট্রিক্স, p, q, n, m)

• আরম্ভ করার জন্য k :=1, যখন k

  • p :=i

  • q =(j + k)

  • যদি ম্যাট্রিক্স[p, q] 1 এর মত হয়, তাহলে:

    • dfs(ম্যাট্রিক্স, p, q, n, m)

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

• n :=ম্যাট্রিক্সের আকার

• উত্তর :=0

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

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

    • যদি ম্যাট্রিক্স[i, j] 1 এর মত হয়, তাহলে:

      • (উত্তর 1 দ্বারা বৃদ্ধি করুন)

      • dfs(ম্যাট্রিক্স, i, j, n, m)

• উত্তর ফেরত দিন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   void dfs(vector<vector<int>>& matrix, int i, int j, int& n, int& m) {
      matrix[i][j] = 2;
      for (int k = 1; k < n; k++) {
         int p = (i + k) % n, q = j;
         if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
      }
      for (int k = 1; k < m; k++) {
         int p = i, q = (j + k) % m;
         if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
      }
   }
   int solve(vector<vector<int>>& matrix) {
      int n = matrix.size(), m = matrix[0].size();
      int ans = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
               ans++;
               dfs(matrix, i, j, n, m);
            }
         }
      }
      return ans;
   }
};

int solve(vector<vector<int>>& matrix) {
   return (new Solution())->solve(matrix);
}

main(){
   vector<vector<int>> v = {
      {1,1,0},
      {0,0,1},
      {1,0,1}
   };
   cout << solve(v);
}

ইনপুট

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

আউটপুট

1