अधिकतम कैंडीज आप C++ के बॉक्स से प्राप्त कर सकते हैं

मान लीजिए कि हमारे पास n बॉक्स हैं, यहाँ प्रत्येक बॉक्स [status, कैंडीज, कीज़, कंटेन्डबॉक्स] जैसे प्रारूप में दिया गया है, कुछ बाधाएँ हैं -

स्थिति [i]:एक 1 है जब बॉक्स [i] खुला होता है और 0 जब बॉक्स [i] बंद होता है।
कैंडीज [i]:बॉक्स [i] में कैंडीज की संख्या है।
कुंजियाँ [i]:एक सरणी है जिसमें उन बक्सों के सूचकांक होते हैं जिन्हें हम बॉक्स [i] में कुंजी के साथ खोल सकते हैं।
निहित बॉक्स [i]:एक सरणी में बॉक्स [i] में पाए गए बक्से के सूचकांक होते हैं।

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

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

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

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

उत्तर:=0
एक कतार को परिभाषित करें q
देखे गए, खोले गए, हैकी सेट को परिभाषित करें
इनिशियलाइज़ करने के लिए:=0, जब i
- एक्स:=आईबी [i]
- विज़िट किए गए में x डालें
- अगर st[x] 1 के समान है, तो -
  - उत्तर:=उत्तर + सीएनटी [एक्स]
  - खुले में x डालें
  - q में x डालें
जबकि (नहीं q खाली है), करें -
- curr :=q का पहला तत्व
- q से तत्व हटाएं
- इनिशियलाइज़ करने के लिए:=0, जब i
  - x :=k[curr, i]
  - हैकी में x डालें
  - यदि x खुला नहीं है और x विज़िट में नहीं है, तो -
    - उत्तर:=उत्तर + सीएनटी [एक्स]
    - q में x डालें
    - खुले में x डालें
- इनिशियलाइज़ करने के लिए:=0, जब i
  - एक्स:=सीबी [कर्र, आई]
  - विज़िट किए गए में x डालें
  - यदि x खुला नहीं है और x hasKey में है या st[x] 1 के समान है, तो -
    - खुले में x डालें
    - उत्तर:=उत्तर + सीएनटी [एक्स]
    - q में x डालें
वापसी उत्तर

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

उदाहरण

#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;
   }
};
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));
}

इनपुट

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