সর্বাধিক ক্যান্ডি আপনি C++ এ বক্স থেকে পেতে পারেন

ধরুন আমাদের n বক্স আছে, এখানে প্রতিটি বক্স ফরম্যাটে দেওয়া আছে যেমন [status, candies, keys, containedBoxes] কিছু সীমাবদ্ধতা আছে −

অবস্থা[i]:বাক্স[i] খোলা থাকলে an হয় 1 এবং বাক্স[i] বন্ধ হলে 0 হয়।
ক্যান্ডি[i]:বাক্সে ক্যান্ডির সংখ্যা।
কী[i]:একটি অ্যারেতে বাক্সের সূচক রয়েছে যা আমরা বাক্সে কী দিয়ে খুলতে পারি।
ধারণকারী বক্সগুলি[i]:একটি অ্যারে বাক্সে পাওয়া বাক্সগুলির সূচকগুলি ধারণ করে।

আমরা ইনিশিয়ালবক্স অ্যারেতে দেওয়া কিছু বক্স দিয়ে শুরু করব। আমরা যেকোন খোলা বাক্সে সমস্ত ক্যান্ডি নিতে পারি এবং নতুন বাক্সগুলি খুলতে আমরা এর চাবিগুলি ব্যবহার করতে পারি এবং আমরা এতে যে বাক্সগুলি পাই তাও ব্যবহার করতে পারি৷

উপরে উল্লিখিত এই নিয়মগুলি অনুসরণ করে আমরা সর্বাধিক কতগুলি ক্যান্ডি পেতে পারি তা আমাদের খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুট হয় স্ট্যাটাস =[1,0,1,0], ক্যান্ডি =[8,6,5,101], এবং কী =[[], [], [1], []], অন্তর্ভুক্ত বক্স =[ [1,2],[3],[],[]], initialBoxes =[0], তারপর আউটপুট হবে 19। এর কারণ হল আমাদের প্রথমে বক্স 0 দেওয়া হবে। আমরা এতে 8টি ক্যান্ডি এবং বক্স পাব। 1 এবং 2. বক্স 1 খোলা হয়নি এবং আমাদের কাছে এটির জন্য একটি চাবি নেই তাই আমরা বক্স 2 খুলব। আমরা বক্স 2 এ 5টি ক্যান্ডি এবং বক্স 1 এর একটি চাবি পাব। বক্স 1 এ, আপনি 6টি ক্যান্ডি পাবেন এবং বক্স 3 কিন্তু আমরা বক্স 3 এর একটি চাবি খুঁজে পাব না তাই বক্স 3 বন্ধ থাকবে। সংগ্রহ করা ক্যান্ডির মোট সংখ্যা =8 + 5 + 6 =19 ক্যান্ডি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

উত্তর :=0
একটি সারি q
সংজ্ঞায়িত করুন
পরিদর্শন করা, খোলা, hasKey
সেট সংজ্ঞায়িত করুন
আরম্ভ করার জন্য i :=0, যখন i
- x :=ib[i]
- পরিদর্শন
  -এ x ঢোকান
- যদি st[x] 1 এর মত হয়, তাহলে −
  - ans :=ans + cnt[x]
  - খোলাতে x ঢোকান
  - q
    -এ x সন্নিবেশ করান
যখন (q খালি নয়), −
করুন
- curr :=q এর প্রথম উপাদান
- q
  থেকে উপাদান মুছুন
- আরম্ভ করার জন্য i :=0, যখন i
  - x :=k[curr, i]
  - hasKey
    -এ x ঢোকান
  - যদি x খোলা না থাকে এবং x পরিদর্শন না হয়, তাহলে −
    - ans :=ans + cnt[x]
    - q
      -এ x সন্নিবেশ করান
    - খোলাতে x ঢোকান
- আরম্ভ করার জন্য i :=0, যখন i
  - x :=cb[curr, i]
  - পরিদর্শন
    -এ x ঢোকান
  - যদি x খোলা না থাকে এবং x hasKey তে থাকে বা st[x] 1 এর মত হয়), তাহলে −
    - খোলাতে x ঢোকান
    - ans :=ans + cnt[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}