資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
