您可以从C ++盒子中获得的最大糖果
假设我们有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