# 1298. Maximum Candies You Can Get from Boxes
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/maximum-candies-you-can-get-from-boxes/
## 思路
找到的盒子不一定有钥匙
有钥匙的盒子不一定找到了
所以要记下已经找到的盒子和已经找到的钥匙
每次有新打开的盒子或者新的钥匙都检查它的钥匙或者它的盒子有没有被打开
## Code

class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[status.length];
        boolean[] found = new boolean[status.length];
        for(int box:initialBoxes){
            found[box] = true;
            if(status[box]==0) continue;
            q.add(box);
            status[box] = -1;
            visited[box] = true;
        }
        
        int candy = 0;
        while(!q.isEmpty()){
            int curr = q.poll();
            candy += candies[curr];
            for(int key:keys[curr]){
                status[key] = 1;
                if(!visited[key] && found[key]){
                    visited[key] = true;
                    q.add(key);
                }
            }
            for(int box:containedBoxes[curr]){
                found[box] = true;
                if(status[box]==1 && !visited[box]){
                    visited[box] = true;
                    q.add(box);
                }
            }
        }
        return candy;
    }
}