原文链接: https://leetcode-cn.com/problems/maximum-candies-you-can-get-from-boxes
英文原文
Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:
status[i]: an integer which is 1 ifbox[i]is open and 0 ifbox[i]is closed.candies[i]: an integer representing the number of candies inbox[i].keys[i]: an array contains the indices of the boxes you can open with the key inbox[i].containedBoxes[i]: an array contains the indices of the boxes found inbox[i].
You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.
Return the maximum number of candies you can get following the rules above.
Example 1:
Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0] Output: 16 Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2. In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed. Total number of candies collected = 7 + 4 + 5 = 16 candy.
Example 2:
Input: 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] Output: 6 Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.
Example 3:
Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1] Output: 1
Example 4:
Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = [] Output: 0
Example 5:
Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0] Output: 7
Constraints:
1 <= status.length <= 1000status.length == candies.length == keys.length == containedBoxes.length == nstatus[i]is0or1.1 <= candies[i] <= 10000 <= keys[i].length <= status.length0 <= keys[i][j] < status.length- All values in
keys[i]are unique. 0 <= containedBoxes[i].length <= status.length0 <= containedBoxes[i][j] < status.length- All values in
containedBoxes[i]are unique. - Each box is contained in one box at most.
0 <= initialBoxes.length <= status.length0 <= initialBoxes[i] < status.length
中文题目
给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中：
- 状态字
status[i]：整数，如果box[i]是开的，那么是 1 ，否则是 0 。 - 糖果数
candies[i]: 整数，表示box[i]中糖果的数目。 - 钥匙
keys[i]：数组，表示你打开box[i]后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。 - 内含的盒子
containedBoxes[i]：整数，表示放在box[i]里的盒子所对应的下标。
给你一个 initialBoxes 数组，表示你现在得到的盒子，你可以获得里面的糖果，也可以用盒子里的钥匙打开新的盒子，还可以继续探索从这个盒子里找到的其他盒子。
请你按照上述规则，返回可以获得糖果的 最大数目 。
示例 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 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。 在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。 你总共可以获得的糖果数目 = 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 和它们对应的钥匙。 打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 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 <= 1000status.length == candies.length == keys.length == containedBoxes.length == nstatus[i]要么是0要么是1。1 <= candies[i] <= 10000 <= keys[i].length <= status.length0 <= keys[i][j] < status.lengthkeys[i]中的值都是互不相同的。0 <= containedBoxes[i].length <= status.length0 <= containedBoxes[i][j] < status.lengthcontainedBoxes[i]中的值都是互不相同的。- 每个盒子最多被一个盒子包含。
0 <= initialBoxes.length <= status.length0 <= initialBoxes[i] < status.length
通过代码
高赞题解
思路
通过广度优先搜索方式来模拟拆盒子的过程。使用队列装入可以被拆开的盒子（状态打开 or 拥有对应钥匙），每次从队列取出一个盒子，并遍历这个盒子里面的内含盒子以及钥匙，遍历的情况包括：
- 内含盒子没有被拆开过，并且有对应钥匙或状态打开，则把它加入队列
- 钥匙所对应的的盒子存在（我们拥有这个盒子），并且盒子没有被拆开，则把它加入队列
Talk is cheap。Show you the code。
代码
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int len = status.length;
// 记录盒子是否被拆开
boolean[] visited = new boolean[len];
// 记录我们拥有的所有盒子
Set<Integer> have_box = new HashSet<>();
// 记录我们拥有的所有钥匙
Set<Integer> have_key = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
// 初始化
for (int i = 0; i < initialBoxes.length; i++) {
int idx = initialBoxes[i];
have_box.add(idx);
// 如果盒子可以打开则加入队列
if (status[idx] == 1) {
q.offer(idx);
visited[idx] = true;
}
}
int ans = 0;
while (!q.isEmpty()) {
Integer cur = q.poll();
ans += candies[cur];
int[] cur_keys = keys[cur];
int[] cur_boxs = containedBoxes[cur];
// 遍历钥匙
for (int key : cur_keys) {
// 加入我们拥有的钥匙列表
have_key.add(key);
// 盒子没被拆开过 且 我们有对应的钥匙
if (!visited[key] && have_box.contains(key)) {
q.offer(key);
visited[key] = true;
}
}
// 遍历内含盒子
for (int box : cur_boxs) {
// 加入我们拥有的盒子列表
have_box.add(box);
// 盒子没被拆开过 且 (我们有对应的钥匙 或者 盒子是打开状态)
if (!visited[box] && (have_key.contains(box) || status[box] == 1)) {
q.offer(box);
visited[box] = true;
}
}
}
return ans;
}
}
如果该题解对你有帮助，点个赞再走呗~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 2726 | 4620 | 59.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
