1298. 你能从盒子里获得的最大糖果数（Rating 1824）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1298. 你能从盒子里获得的最大糖果数

Rating 1824

思路

模拟（或bfs），维护以下几个变量即可

• 手里未打开的box
• 手里未使用的key
• 手里已使用的box
• 手里已使用的key

代码

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        my_box = {box for box in initialBoxes} # 手里未打开的box
        my_key = set()
        ret = 0
        while True:
            opened_box = [] # 本次打开的box
            used_key = [] # 本次使用的key
            new_box = [] # 本次新获得的box
            new_key = [] # 本次新获得的key
            for box in my_box: # 遍历手中未打开的box
                if status[box] == 1 or box in my_key: # 如果box是开的，或者手中有key
                    ret += candies[box] # 获得其中的candy
                    opened_box.append(box) # 更新已打开的box
                    for nb in containedBoxes[box]: # 更新新获得的box
                        new_box.append(nb)
                    for nk in keys[box]: # 更新新获得的key
                        new_key.append(nk)
                    if status[box] == 0 and box in my_key: # 如果box是关的，且手中有key
                        used_key.append(box) # 更新已使用的key
            if not opened_box: # 如果已经没有可以打开的box了，返回答案
                return ret
            for rb in opened_box: # 更新my_box
                my_box.remove(rb)
            for rk in used_key: # 更新my_key
                my_key.remove(rk)
            for nb in new_box: # 更新my_box
                my_box.add(nb)
            for nk in new_key: # 更新my_key
                my_key.add(nk)