Số kẹo tối đa bạn có thể nhận được từ hộp trong C ++

Giả sử chúng ta có n hộp, ở đây mỗi hộp được đưa ra ở định dạng như [trạng thái, kẹo, khóa, hộp chứa] có một số ràng buộc -

trạng thái [i]:an là 1 khi hộp [i] đang mở và 0 khi hộp [i] đóng.
candy [i]:là số lượng kẹo trong hộp [i].
key [i]:là một mảng chứa các chỉ số của các hộp mà chúng ta có thể mở bằng khóa trong hộp [i].
containsBoxes [i]:một mảng chứa các chỉ số của các hộp được tìm thấy trong hộp [i].

Chúng ta sẽ bắt đầu với một số hộp được đưa ra trong mảng initialBoxes. Chúng ta có thể lấy tất cả kẹo trong bất kỳ hộp nào đang mở và chúng ta có thể sử dụng các chìa khóa trong đó để mở các hộp mới và chúng ta cũng có thể sử dụng các hộp mà chúng ta tìm thấy trong đó.

Chúng ta phải tìm số kẹo tối đa mà chúng ta có thể nhận được theo các quy tắc đã đề cập ở trên.

Vì vậy, nếu đầu vào giống như trạng thái =[1,0,1,0], candy =[8,6,5.101] và các khóa =[[], [], [1], []], containsBoxes =[ [1,2], [3], [], []], initialBoxes =[0], thì kết quả đầu ra sẽ là 19. Điều này là do ban đầu chúng ta sẽ được cung cấp hộp 0. Chúng ta sẽ tìm thấy 8 viên kẹo trong đó và các hộp Hộp 1 và 2. Hộp 1 không được mở và chúng ta không có chìa khóa cho nó nên chúng ta sẽ mở hộp 2. Chúng ta sẽ tìm thấy 5 viên kẹo và chìa khóa vào hộp 1 trong hộp 2. Trong hộp 1, bạn sẽ tìm thấy 6 viên kẹo và hộp 3 nhưng chúng tôi sẽ không tìm thấy chìa khóa cho hộp 3 vì vậy hộp 3 sẽ vẫn đóng. Tổng số kẹo thu được =8 + 5 + 6 =19 viên kẹo.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ans:=0
Xác định một hàng đợi q
Xác định các nhóm đã truy cập, đã mở, hasKey
để khởi tạo i:=0, khi tôi
- x:=ib [i]
- chèn x vào đã truy cập
- nếu st [x] giống với 1 thì -
  - ans:=ans + cnt [x]
  - chèn x vào đã mở
  - chèn x vào q
while (không phải q trống), do -
- curr:=phần tử đầu tiên của q
- xóa phần tử khỏi q
- để khởi tạo i:=0, khi i
  - x:=k [curr, i]
  - chèn x vào hasKey
  - nếu x không được mở và x không được truy cập, thì -
    - ans:=ans + cnt [x]
    - chèn x vào q
    - chèn x vào đã mở
- để khởi tạo i:=0, khi tôi
  - x:=cb [curr, i]
  - chèn x vào đã truy cập
  - nếu x không ở trong đã mở và x ở trong hasKey hoặc st [x] giống với 1), thì -
    - chèn x vào đã mở
    - ans:=ans + cnt [x]
    - chèn x vào q
trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Số kẹo tối đa bạn có thể nhận được từ hộp trong C ++

Ví dụ

Đầu vào

Đầu ra