数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中从盒子中获取的最大糖果数
假设我们有 n 个盒子，每个盒子都以 [状态，糖果，钥匙，包含的盒子] 的格式给出，有一些约束条件：
status[i]：当 box[i] 打开时为 1，当 box[i] 关闭时为 0。
candies[i]：是 box[i] 中糖果的数量。
keys[i]：是一个数组，包含 box[i] 中的钥匙可以打开的盒子的索引。
containedBoxes[i]：是一个数组，包含 box[i] 中找到的盒子的索引。
我们将从 initialBoxes 数组中给出的某些盒子开始。我们可以取任何打开的盒子中的所有糖果，并且可以使用其中的钥匙打开新的盒子，我们还可以使用我们在其中找到的盒子。
我们必须找到按照上述规则可以获得的最大糖果数量。
因此，如果输入类似于 status = [1,0,1,0]，candies = [8,6,5,101]，以及 keys = [[], [], [1], []]，containedBoxes = [[1,2],[3],[],[]]，initialBoxes = [0]，则输出将为 19。这是因为我们将最初获得盒子 0。我们将在其中找到 8 个糖果和盒子 1 和 2。盒子 1 未打开，我们没有它的钥匙，因此我们将打开盒子 2。我们将在盒子 2 中找到 5 个糖果和盒子 1 的钥匙。在盒子 1 中，您将找到 6 个糖果和盒子 3，但我们不会找到盒子 3 的钥匙，因此盒子 3 将保持关闭状态。收集到的糖果总数 = 8 + 5 + 6 = 19 个糖果。
为了解决这个问题，我们将遵循以下步骤：
ans := 0
定义一个队列 q
定义集合 visited、opened、hasKey
初始化 i := 0，当 i < ib 的大小，更新（i 增加 1），执行：
x := ib[i]
将 x 插入 visited
如果 st[x] 与 1 相同，则：
ans := ans + cnt[x]
将 x 插入 opened
将 x 插入 q
当 (q 不为空) 时，执行：
curr := q 的第一个元素
从 q 中删除元素
初始化 i := 0，当 i < k[curr] 的大小，更新（i 增加 1），执行：
x := k[curr, i]
将 x 插入 hasKey
如果 x 不在 opened 中且 x 不在 visited 中，则：
ans := ans + cnt[x]
将 x 插入 q
将 x 插入 opened
初始化 i := 0，当 i < cb[curr] 的大小，更新（i 增加 1），执行：
x := cb[curr, i]
将 x 插入 visited
如果 x 不在 opened 中且 x 在 hasKey 中或 st[x] 与 1 相同，则：
将 x 插入 opened
ans := ans + cnt[x]
将 x 插入 q
返回 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
311 次查看
