सी++ में संचार टावरों में समूहों की न्यूनतम संख्या खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास 2 डी बाइनरी मैट्रिक्स है जहां 1 संचार टावर का प्रतिनिधित्व करता है, और 0 एक खाली सेल का प्रतिनिधित्व करता है। टावर निम्नलिखित तरीकों से संचार कर सकते हैं:1. यदि टावर ए, और टावर बी या तो एक ही पंक्ति या कॉलम पर हैं, तो वे एक दूसरे के साथ संवाद कर सकते हैं। 2. यदि टावर ए टावर बी से बात कर सकता है और बी सी के साथ बात कर सकता है, तो ए सी (संक्रमणीय संपत्ति) से बात कर सकता है। हमें वहां टावर समूहों की कुल संख्या ज्ञात करनी है (यहां एक समूह टावरों की एक सूची है जो एक दूसरे के साथ बात कर सकते हैं)।

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

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

• फ़ंक्शन dfs() को परिभाषित करें, यह एक 2D सरणी मैट्रिक्स, i, j, n, m,

  लेगा

• मैट्रिक्स [i, j] :=2

• k :=1 को इनिशियलाइज़ करने के लिए, जब k

  • p :=(i + k) मॉड n

  • क्यू:=जे

  • यदि मैट्रिक्स [p, q] 1 के समान है, तो:

    • डीएफएस (मैट्रिक्स, पी, क्यू, एन, एम)

• k :=1 को इनिशियलाइज़ करने के लिए, जब k

  • पी:=मैं

  • क्यू =(जे + के)

  • यदि मैट्रिक्स [p, q] 1 के समान है, तो:

    • डीएफएस (मैट्रिक्स, पी, क्यू, एन, एम)

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

• n :=मैट्रिक्स का आकार

• उत्तर :=0

• इनिशियलाइज़ करने के लिए:=0, जब मैं

  • प्रारंभ करने के लिए j :=0, जब j

    • यदि मैट्रिक्स [i, j] 1 के समान है, तो:

      • (उत्तर 1 से बढ़ाएँ)

      • डीएफएस (मैट्रिक्स, आई, जे, एन, एम)

• वापसी उत्तर

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

उदाहरण

#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