526互联

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

发布时间 2023-04-12 20:36:22作者: zhangk1988

题目描述

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

f1-模拟 + bfs

基本分析

  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]) -&gt; 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. 在打开每个盒子的时候，枚举钥匙和盒子时候，先要更新拥有状态，在看能不能继续拆（入队）