Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:
status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
candies[i]: an integer representing the number of candies in box[i].
keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
containedBoxes[i]: an array contains the indices of the boxes found in box[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 <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] is 0 or 1.
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
All values in keys[i] are unique.
0 <= containedBoxes[i].length <= status.length
0 <= 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.length
0 <= initialBoxes[i] < status.length
class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        
        
        #Approach 1:  use set 
        #The queue only contains boxes which is accessible
        q=collections.deque()
        
        #Important initiation,consider all opens box equivalent to they have keys
        keys_set=set([i for i in range(len(status)) if status[i]==1])   #Set for all available keys
        boxes_set=set(initialBoxes[:])  #set for all boxes that we have seen
        
        #Initialize the queue to process box
        for box in initialBoxes:
            if(box in keys_set):  #Status[box]==1 is equivalent to it has a key
                q.append(box)

        res=0
        visited=set()   #More universal for all test cases, record all the boxes that have been processed
        #use DFS to populate the queue
        while q:
            
            boxi=q.popleft()
            #Avoid duplicated count
            if(boxi in visited):
                continue
            else:
                visited.add(boxi)
                res +=candies[boxi]
                
            #Check all neighbors of current boxi
            for nei in containedBoxes[boxi]:
                if(nei in keys_set):  #it is either open or has key
                    q.append(nei)
                boxes_set.add(nei)
                
            #Check all keys of current boxi
            for key in keys[boxi]:
                #Only append the box index wich has not been considered, because there is no key, but it is in the boxes_set
                if(key in boxes_set and (key not in keys_set)):
                    q.append(key) 
                keys_set.add(key)
                
        return res
    
    
        #Approach 2: use list
        
#         haskeys=status[:]
#         seen=[0]*len(status)
#         q=collections.deque()   #Only contains boxes that are accessible
        
#         for box in initialBoxes:
#             seen[box]=1
#             if(haskeys[box]):
#                 q.append(box)   #Include the one only accessible
                
#         res=0
#         visited=set()
#         while q:
            
#             boxi=q.popleft()
#             if(boxi in visited):
#                 continue
#             else:
#                 visited.add(boxi)
#                 res+=candies[boxi]
            
#             #Since eachbox is contained in one box at most
#             #it will not result in duplicated elements in q
#             for nei in containedBoxes[boxi]:
#                 seen[nei]=1
#                 if(haskeys[nei]): q.append(nei)
            
#             #Iterate through all available keys, 
#             #inlcude the box has been seen but doesn't have key to the queue
#             for key in keys[boxi]:
#                 if(seen[key] and haskeys[key]==0):  #Meaning it has not been included in queue
#                     q.append(key)
#                 haskeys[key]=1
        
#         return res
                    
                
            
            
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
            
            
            

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        
        
        #Approach 1:  use set 
        #The queue only contains boxes which is accessible
        q=collections.deque()
        
        #Important initiation,consider all opens box equivalent to they have keys
        keys_set=set([i for i in range(len(status)) if status[i]==1])   #Set for all available keys
        boxes_set=set(initialBoxes[:])  #set for all boxes that we have seen
        
        #Initialize the queue to process box
        for box in initialBoxes:
            if(box in keys_set):  #Status[box]==1 is equivalent to it has a key
                q.append(box)

        res=0
        visited=set()   #More universal for all test cases, record all the boxes that have been processed
        #use DFS to populate the queue
        while q:
            
            boxi=q.popleft()
            #Avoid duplicated count
            if(boxi in visited):
                continue
            else:
                visited.add(boxi)
                res +=candies[boxi]
                
            #Check all neighbors of current boxi
            for nei in containedBoxes[boxi]:
                if(nei in keys_set):  #it is either open or has key
                    q.append(nei)
                boxes_set.add(nei)
                
            #Check all keys of current boxi
            for key in keys[boxi]:
                #Only append the box index wich has not been considered, because there is no key, but it is in the boxes_set
                if(key in boxes_set and (key not in keys_set)):
                    q.append(key) 
                keys_set.add(key)
                
        return res
    
    
        #Approach 2: use list
        
#         haskeys=status[:]
#         seen=[0]*len(status)
#         q=collections.deque()   #Only contains boxes that are accessible
        
#         for box in initialBoxes:
#             seen[box]=1
#             if(haskeys[box]):
#                 q.append(box)   #Include the one only accessible
                
#         res=0
#         visited=set()
#         while q:
            
#             boxi=q.popleft()
#             if(boxi in visited):
#                 continue
#             else:
#                 visited.add(boxi)
#                 res+=candies[boxi]
            
#             #Since eachbox is contained in one box at most
#             #it will not result in duplicated elements in q
#             for nei in containedBoxes[boxi]:
#                 seen[nei]=1
#                 if(haskeys[nei]): q.append(nei)
            
#             #Iterate through all available keys, 
#             #inlcude the box has been seen but doesn't have key to the queue
#             for key in keys[boxi]:
#                 if(seen[key] and haskeys[key]==0):  #Meaning it has not been included in queue
#                     q.append(key)
#                 haskeys[key]=1
        
#         return res
                    
                
            
            
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
            
            
            
