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

C++ में बक्सों से अधिकतम कैंडी प्राप्त करना

मान लीजिए हमारे पास n बक्से हैं, यहां प्रत्येक बॉक्स को प्रारूप में दिया गया है जैसे [status, candies, keys, containedBoxes] कुछ प्रतिबंधों के साथ:

  • status[i]: 1 जब box[i] खुला है और 0 जब box[i] बंद है।

  • candies[i]: box[i] में कैंडी की संख्या।

  • keys[i]: उन बक्सों के इंडेक्स की एक सरणी जिन्हें हम box[i] में कुंजी से खोल सकते हैं।

  • containedBoxes[i]: box[i] में पाए जाने वाले बक्सों के इंडेक्स की एक सरणी।

हम initialBoxes सरणी में दिए गए कुछ बक्सों से शुरू करेंगे। हम किसी भी खुले बॉक्स में सभी कैंडी ले सकते हैं और हम इसमें कुंजियों का उपयोग नए बक्से खोलने के लिए कर सकते हैं और हम इसमें मिले बक्सों का भी उपयोग कर सकते हैं।

हमें उपरोक्त नियमों का पालन करते हुए प्राप्त की जा सकने वाली कैंडी की अधिकतम संख्या ज्ञात करनी है।

यदि इनपुट status = [1,0,1,0], candies = [8,6,5,101], keys = [[], [], [1], []], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0] है, तो आउटपुट 19 होगा। ऐसा इसलिए क्योंकि हमें शुरू में बॉक्स 0 दिया जाता है। हम इसमें 8 कैंडी और बक्से 1 और 2 पाते हैं। बॉक्स 1 खुला नहीं है और हमारे पास इसकी कुंजी नहीं है इसलिए हम बॉक्स 2 खोलेंगे। बॉक्स 2 में हमें 5 कैंडी और बॉक्स 1 की कुंजी मिलती है। बॉक्स 1 में, हमें 6 कैंडी और बॉक्स 3 मिलता है लेकिन हमें बॉक्स 3 की कुंजी नहीं मिलती इसलिए बॉक्स 3 बंद रहेगा। एकत्र की गई कुल कैंडी = 8 + 5 + 6 = 19 कैंडी।

हल करने के चरण

  • ans := 0, एक कतार q, सेट visited, opened, hasKey परिभाषित करें

  • प्रारंभिक बक्सों के लिए: visited में डालें, यदि खुला है तो कैंडी जोड़ें, opened में डालें, कतार में डालें

  • जब तक कतार खाली नहीं: वर्तमान बॉक्स निकालें, इसकी कुंजियों को hasKey में डालें, यदि कुंजी वाला बॉक्स visited में है लेकिन opened में नहीं तो खोलें

  • समाहित बक्सों को visited में डालें, यदि कुंजी है या खुला है तो खोलें

  • ans लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int maxCandies(vector<int>& st, vector<int>& cnt, vector<vector<int>>& k, vector<vector<int>>& cb, vector<int>& ib) { 
        int ans = 0; 
        queue<int> q; 
        set<int> visited; 
        set<int> opened; 
        set<int> hasKey; 
        for (int i = 0; i < ib.size(); i++) { 
            int x = ib[i]; 
            visited.insert(x); 
            if (st[x] == 1) { 
                ans += cnt[x]; 
                opened.insert(x); 
                q.push(x); 
            } 
        } 
        while (!q.empty()) { 
            int curr = q.front(); 
            q.pop(); 
            for (int i = 0; i < k[curr].size(); i++) { 
                int x = k[curr][i]; 
                hasKey.insert(x); 
                if (!opened.count(x) && visited.count(x)) { 
                    ans += cnt[x]; 
                    q.push(x); 
                    opened.insert(x); 
                } 
            } 
            for (int i = 0; i < cb[curr].size(); i++) { 
                int x = cb[curr][i]; 
                visited.insert(x); 
                if (!opened.count(x) && (hasKey.count(x) || st[x] == 1)) { 
                    opened.insert(x); 
                    ans += cnt[x]; 
                    q.push(x); 
                } 
            } 
        } 
        return ans; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {1,0,1,0}, v1 = {8,6,5,101}, v2 = {0}; 
    vector<vector<int>> v3 = {{},{},{1},{}}, v4 = {{1,2},{3},{0},{}}; 
    cout << (ob.maxCandies(v, v1, v3, v4, v2)); 
    return 0; 
}

इनपुट

{1,0,1,0}, {8,6,5,101}, {{},{},{1},{}}, {{1,2},{3},{0},{}}, {0}

आउटपुट

19
  1. C++ में N*N शतरंज बोर्ड पर रखे जा सकने वाले अधिकतम बिशप की संख्या C++ में N*N शतरंज बोर्ड पर रखे जा सकने वाले अधिकतम बिशप की संख्या

    हमें एक इनपुट N दिया गया है जो शतरंज बोर्ड के आकार को दर्शाता है। यहां कार्य N के किसी भी मान के लिए यह पता लगाना है कि NxN शतरंज बोर्ड पर कितने बिशप रखे जा सकते हैं ताकि कोई भी दो बिशप एक-दूसरे पर हमला न कर सकें।उदाहरण से समझते हैंइनपुट - N=2आउटपुट - N*N शतरंज बोर्ड पर रखे जा सकने वाले अधिकतम बिशप

  1. - C++ में सेट में जोड़े जा सकने वाले अधिकतम अंतर वाले एलिमेंट्स

    समस्या के अनुसार हमें एक सेट arr[n] दिया गया है जहां n सेट में पूर्णांक एलिमेंट्स की संख्या है, कार्य उन अधिकतम अंतर वाले एलिमेंट्स को ढूंढना है जिन्हें सेट में एलिमेंट्स प्राप्त करने के लिए जोड़ा जाना है। दूसरे शब्दों में, अंतर |a-b| के रूप में होना चाहिए जहां a और b दोनों सेट में हों और उनका अंतर

  1. C++ में अधिकतम दर्पण जो प्रकाश को नीचे से दाएं स्थानांतरित कर सकते हैं C++ में अधिकतम दर्पण जो प्रकाश को नीचे से दाएं स्थानांतरित कर सकते हैं

    हमें एक वर्ग मैट्रिक्स दिया गया है जिसमें केवल 0 और 1 हैं। 0 खाली स्थान दर्शाता है और 1 बाधा दर्शाता है। हमें खाली सेल पर रखे जा सकने वाले दर्पणों की संख्या ढूंढनी होगी ताकि ये दर्पण प्रकाश को नीचे से दाएं स्थानांतरित कर सकें। यह तब संभव है जब, दर्पण इंडेक्स [i,j] पर रखा गया हो और उस विशेष पंक्ति (i