世界观焦点：1298. 你能从盒子里获得的最大糖果数

(相关资料图)

题目描述

一个盒子有四种属性，能否打开、糖果数、钥匙、内含盒子给你初始盒子的索引，问能拿到多少糖果？

基本分析

1. 一个索引需要有哪些状态？能不能打开；是不是有了这个盒子；这个盒子打开过没有？
2. 怎么定义这些状态？数组
3. bfs的规则？（1）最初入队？如果盒子能打开，把盒子入队（入队以后看里面的盒子和钥匙），入队前累加糖果；（2）怎么开盒子？
   • <1>.枚举每个钥匙，先更新钥匙的拥状态；如果没拆过+有盒子，就入队钥匙索引；
   • <2> 枚举每个盒子，先更新盒子的拥有状态，如果没拆过+有钥匙，就入队盒子索引

代码

class Solution:    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:        n = len(status)        has_box = [False] * n        vis = [False] * n        can_open = [status[i] == 1 for i in range(n)]        q = deque([])        ans = 0                for box in initialBoxes:            has_box[box] = True            if can_open[box]:                q.append(box)                vis[box] = True                ans += candies[box]        # 队列中的是啥，可以打开的盒子，他的值已经被计算了        while q:            cur = q.popleft()            for key in keys[cur]:                can_open[key] = True                if not vis[key] and has_box[key]:                    ans += candies[key]                    q.append(key)                    vis[key] = True                        for box in containedBoxes[cur]:                has_box[box] = True                if not vis[box] and can_open[box]:                    ans += candies[box]                    q.append(box)                    vis[box] = True                return ans

总结

1. 索引对应的状态很多，需要定义清楚
2. 最开始给的初始盒子，没有和盒子平级的钥匙
3. 在打开每个盒子的时候，枚举钥匙和盒子时候，先要更新拥有状态，在看能不能继续拆（入队）

关键词：