C++의 상자에서 얻을 수 있는 최대 사탕

<시간/>

n개의 상자가 있다고 가정하고 여기서 각 상자는 [상태, 사탕, 키, 포함된 상자]와 같은 형식으로 제공됩니다. 몇 가지 제약 조건이 있습니다. −

status[i]:an은 box[i]가 열려 있을 때 1이고 box[i]가 닫혀 있을 때 0입니다.
사탕[i]:상자[i]에 들어 있는 사탕의 수입니다.
keys[i]:배열은 box[i]의 키로 열 수 있는 상자의 인덱스를 포함합니다.
includedBoxes[i]:배열은 box[i]에서 찾은 상자의 인덱스를 포함합니다.

initialBoxes 배열에 제공된 몇 가지 상자부터 시작하겠습니다. 열린 상자에 있는 모든 사탕을 가져갈 수 있고, 그 안에 있는 열쇠를 사용하여 새 상자를 열 수 있고, 그 안에 있는 상자를 사용할 수도 있습니다.

위에서 언급한 이러한 규칙에 따라 얻을 수 있는 최대 사탕 수를 찾아야 합니다.

따라서 입력이 상태 =[1,0,1,0], 사탕 =[8,6,5,101] 및 키 =[[], [], [1], []], includedBoxes =[ [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 세트 정의
initialize i :=0의 경우, i
- x :=ib[i]
- 방문에 x 삽입
- st[x]가 1과 같으면 -
  - ans :=ans + cnt[x]
  - 열린 부분에 x 삽입
  - q에 x 삽입
동안(q가 비어 있지 않음) -
를 수행합니다.
- curr :=q의 첫 번째 요소
- q에서 요소 삭제
- for initialize i :=0, i
  - x :=k[curr, i]
  - x를 hasKey에 삽입
  - x가 열려 있지 않고 x가 방문하지 않은 경우 -
    - ans :=ans + cnt[x]
    - q에 x 삽입
    - 열린 부분에 x 삽입
- initialize 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}