Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में कम्युनिकेशन टावर्स में न्यूनतम समूहों की संख्या


मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है जहां 1 एक कम्युनिकेशन टावर को दर्शाता है, और 0 एक खाली सेल को दर्शाता है। टावर निम्न तरीकों से संवाद कर सकते हैं:

  1. यदि टावर A और टावर B एक ही पंक्ति या कॉलम पर हैं, तो वे एक-दूसरे से संवाद कर सकते हैं।
  2. यदि टावर A, टावर B से बात कर सकता है और B, C से बात कर सकता है, तो A, C से बात कर सकता है (संक्रामक गुण)।

हमें टावर समूहों की कुल संख्या ज्ञात करनी है (एक समूह उन टावर्स की सूची है जो एक-दूसरे से बात कर सकते हैं)।

उदाहरण के लिए, इनपुट मैट्रिक्स:

110
001
101

आउटपुट 1 होगा क्योंकि सभी टावर एक-दूसरे से जुड़े हुए हैं।

समाधान दृष्टिकोण (DFS)

  • dfs() फ़ंक्शन परिभाषित करें जो मैट्रिक्स, i, j, n, m लेता है।
  • matrix[i][j] := 2 (विज़िटेड मार्क करें)।
  • उसी कॉलम में सभी पंक्तियों k के लिए: p = (i+k)%n, q = j; यदि matrix[p][q] == 1 तो DFS कॉल करें।
  • उसी पंक्ति में सभी कॉलम k के लिए: p = i, q = (j+k)%m; यदि matrix[p][q] == 1 तो DFS कॉल करें।
  • मेन मेथड में: सभी सेल्स को पार करें, यदि 1 मिले तो ans++ करें और DFS कॉल करें।

उदाहरण (C++ कोड)

#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 main() { 
    vector<vector<int>> v = {{1,1,0}, {0,0,1}, {1,0,1}}; 
    cout << (new Solution())->solve(v); 
    return 0; 
}

इनपुट

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

आउटपुट

1

  1. - C++ में Nवीं सम फाइबोनैचि संख्या खोजने का प्रोग्राम

    समस्या विवरण इस समस्या में, हमें एक पूर्णांक मान N दिया गया है। हमारा कार्य Nवीं सम फाइबोनैचि संख्या खोजना है। फाइबोनैचि श्रृंखला पिछली दो संख्याओं को जोड़कर बाद की संख्या उत्पन्न करती है। फाइबोनैचि श्रृंखला दो संख्याओं से शुरू होती है - F0 और F1। F0 और F1 के प्रारंभिक मान 0, 1 या 1, 1 लिए जा सकते

  1. - C++ प्रोग्राम श्रृंखला 1, 6, 15, 28, 45, ….. का Nवां नंबर ढूंढने के लिए

    इस समस्या में, हमें एक पूर्णांक मान N दिया जाता है। हमारा कार्य श्रृंखला 1, 6, 15, 28, 45, … का Nवां नंबर ढूंढने के लिए एक प्रोग्राम बनाना है।श्रृंखला में, प्रत्येक तत्व पिछले और अगले तत्व के माध्य से 2 कम होता है।आइए एक उदाहरण से समस्या को समझते हैं,इनपुटN = 5आउटपुट45समाधान दृष्टिकोणश्रृंखला 1, 6,

  1. C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम

    परिचय मान लीजिए हमारे पास ट्री एजेज की एक सूची है [u, v] के रूप में, जो इंगित करती है कि u और v के बीच एक अनडायरेक्टेड एज है। और हमारे पास दो मान x और y भी हैं। यदि हम नोड x पर हैं, और हमारा प्रतिद्वंद्वी नोड y पर है। पहले राउंड में हम चलते हैं, फिर अगले राउंड में प्रतिद्वंद्वी चलता है और इसी तरह।