假设我们有n个盒子，这里每个盒子都以[状态，糖果，键，containedBoxes]之类的格式给出，但有一些约束-
status [i]：打开box [i]时为1，关闭box [i]时为0。
candies [i]：是box [i]中的糖果数。
keys [i]：是一个数组，其中包含我们可以使用box [i]中的键打开的盒子的索引。
containsBoxes [i]：一个数组，其中包含在box [i]中找到的盒子的索引。
我们将从initialBoxes数组中给出的一些盒子开始。我们可以将所有糖果放入任何打开的盒子中，并且可以使用其中的键来打开新盒子，也可以使用在其中找到的盒子。
我们必须找到遵循上述规则可获得的最大糖果数量。
因此，如果输入的状态为[1,0,1,0]，糖果= [8,6,5,101]，键= [[]，[]，[1]，[]]，则containsBoxes = [ [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 <ib的大小时，更新（将i增加1），执行-
ans：= ans + cnt [x]
将x插入打开
将x插入q
x：= ib [i]
将x插入已访问
如果st [x]与1相同，则-
当（不是q为空）时，执行-
x：= cb [curr，i]
将x插入已访问
如果x未打开且x在hasKey或st [x]与1相同，则-
将x插入打开
ans：= ans + cnt [x]
将x插入q
x：= k [curr，i]
将x插入hasKey
如果x未打开且x未访问，则-
ans：= ans + cnt [x]
将x插入q
将x插入打开
curr：= q的第一个元素
从q删除元素
对于初始化i：= 0，当i <k [curr]的大小时，更新（将i增加1），执行-
对于初始化i：= 0，当i <cb [curr]的大小时，更新（将i增加1），执行-
返回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