文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你 n 個盒子，每個盒子的格式為 [status, candies, keys, containedBoxes] ，其中：

- 狀態(tài)字 status[i]：整數(shù)，如果 box[i] 是開的，那么是 1 ，否則是 0 。 - 糖果數(shù) candies[i]: 整數(shù)，表示 box[i] 中糖果的數(shù)目。 - 鑰匙 keys[i]：數(shù)組，表示你打開 box[i] 后，可以得到一些盒子的鑰匙，每個元素分別為該鑰匙對應盒子的下標。 - 內含的盒子 containedBoxes[i]：整數(shù)，表示放在 box[i] 里的盒子所對應的下標。 - 給你一個 initialBoxes 數(shù)組，表示你現(xiàn)在得到的盒子，你可以獲得里面的糖果，也可以用盒子里的鑰匙打開新的盒子，還可以繼續(xù)探索從這個盒子里找到的其他盒子。

請你按照上述規(guī)則，返回可以獲得糖果的 最大數(shù)目 。

示例 1： 輸入： status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0] 輸出：16 解釋： 一開始你有盒子 0 。你將獲得它里面的 7 個糖果和盒子 1 和 2。 盒子 1 目前狀態(tài)是關閉的，而且你還沒有對應它的鑰匙。 所以你將會打開盒子 2 ，并得到里面的 4 個糖果和盒子 1 的鑰匙。 在盒子 1 中，你會獲得 5 個糖果和盒子 3 ， 但是你沒法獲得盒子 3 的鑰匙所以盒子 3 會保持關閉狀態(tài)。 你總共可以獲得的糖果數(shù)目 = 7 + 4 + 5 = 16 個。示例 2： 輸入： status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0] 輸出：6 解釋： 你一開始擁有盒子 0 。打開它你可以找到盒子 1,2,3,4,5 和它們對應的鑰匙。 打開這些盒子，你將獲得所有盒子的糖果，所以總糖果數(shù)為 6 個。示例 3： 輸入：status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1] 輸出：1示例 4： 輸入：status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = [] 輸出：0示例 5： 輸入：status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0] 輸出：7提示： 1 <= status.length <= 1000 status.length == candies.length == keys.length == containedBoxes.length == n status[i] 要么是 0 要么是 1 。 1 <= candies[i] <= 1000 0 <= keys[i].length <= status.length 0 <= keys[i][j] < status.length keys[i] 中的值都是互不相同的。 0 <= containedBoxes[i].length <= status.length 0 <= containedBoxes[i][j] < status.length containedBoxes[i] 中的值都是互不相同的。 每個盒子最多被一個盒子包含。 0 <= initialBoxes.length <= status.length 0 <= initialBoxes[i] < status.length

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-candies-you-can-get-from-boxes
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 廣度優(yōu)先搜索，使用哈希set記錄已經(jīng)遍歷到的盒子，但是還沒有鑰匙的

class Solution { public:int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {queue<int> q;int sum = 0, id;unordered_set<int> nokeybox;for(int box : initialBoxes){q.push(box);}while(!q.empty()){id = q.front();q.pop();sum += candies[id];for(int k : keys[id]){status[k] = 1;//這個盒子可以打開的if(nokeybox.count(k)){ //沒有鑰匙的盒子有鑰匙了q.push(k);//入隊nokeybox.erase(k);}}for(int box : containedBoxes[id]){if(status[box]==1)q.push(box);elsenokeybox.insert(box);}}return sum;} };

264 ms 30.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1298. 你能从盒子里获得的最大糖果数（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。