मान लीजिए हमारे पास 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