ধরি nটি বাক্স আছে, প্রতিটি বাক্স [status, candies, keys, containedBoxes] ফরম্যাটে। status[i]=1 হলে খোলা, 0 হলে বন্ধ। candies[i]=ক্যান্ডির সংখ্যা। keys[i]=যে বাক্সগুলো খোলা যাবে তার ইন্ডেক্স। containedBoxes[i]=বাক্সের ভেতরে পাওয়া যাবে বাক্সগুলোর ইন্ডেক্স। initialBoxes অ্যারে থেকে শুরু করে ন্যূনতম ক্যান্ডি সংগ্রহ করতে হবে।
ইনপুট: status=[1,0,1,0], candies=[8,6,5,101], keys=[[],[],[1],[]], containedBoxes=[[1,2],[3],[],[]], initialBoxes=[0] → আউটপুট 19।
সমাধানের ধাপসমূহ
ans := 0, q := কিউ, visited, opened, hasKey := সেট
initialBoxes-এ থাকা বাক্সগুলো visited-এ যোগ করুন, খোলা থাকলে ক্যান্ডি যোগ করে q-তে ঢুকান
q খালি না হওয়া পর্যন্ত –
curr := q থেকে বের করুন
curr-র চাবিগুলো hasKey-এ যোগ করুন, ভিজিট করা বাক্স খোলা যায় তবে খুলুন
curr-র containedBoxes গুলো 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; } }; 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}আউটপুট
19
