Count Candies from Unlockable Boxes

Problem Statement

You are given n boxes, numbered from 0 to n - 1. Each box i contains a certain number of candies, keys to other boxes, and other boxes inside it.

You are given the following arrays:

• status: An array of integers where status[i] = 1 if box i is already unlocked (open), and status[i] = 0 if box i is locked.
• candies: An array of integers where candies[i] is the number of candies in box i.
• keys: A 2D array where keys[i] is a list of box IDs that can be unlocked using the keys found in box i.
• contained_boxes: A 2D array where contained_boxes[i] is a list of box IDs contained inside box i.
• initial_boxes: An array of box IDs that you initially have in your possession.

A box can only be opened if you currently have it in your possession and it is unlocked (either because it was initially unlocked or you obtained its key). Once you open a box:

1. You collect all its candies.
2. You obtain all the keys contained inside it (which unlock corresponding locked boxes).
3. You obtain all the boxes contained inside it into your possession.

Return the total number of candies you can collect.

Function Signature

def max_candies(
    status: list[int],
    candies: list[int],
    keys: list[list[int]],
    contained_boxes: list[list[int]],
    initial_boxes: list[int]
) -> int:
    pass

Examples

Example 1

status = [1, 0, 1, 0]
candies = [7, 5, 4, 100]
keys = [[], [], [1], []]
contained_boxes = [[1, 2], [3], [], []]
initial_boxes = [0]

# Output: 16

Explanation:

• Initially, you have box 0, which is unlocked (status[0] == 1). You open it and get 7 candies, no keys, and boxes 1 and 2.
• Box 2 is unlocked (status[2] == 1), so you open it and get 4 candies, a key to box 1, and no new boxes.
• Box 1 is now possessed and unlocked via the key from box 2. You open box 1, getting 5 candies, no keys, and box 3.
• Box 3 is possessed, but it is locked (status[3] == 0) and you have no key for it, so you cannot open it.
• Total candies collected = 7 + 4 + 5 = 16.

Example 2

status = [1, 1, 1]
candies = [100, 1, 100]
keys = [[], [0, 2], []]
contained_boxes = [[], [], []]
initial_boxes = [1]

# Output: 1

Explanation:

• You start with box 1, which is unlocked. You get 1 candy and keys to boxes 0 and 2.
• However, you never obtain boxes 0 or 2 in your possession, so you cannot open them.
• Total candies collected = 1.

Constraints

• n == status.length == candies.length == keys.length == contained_boxes.length
• 1 <= n <= 1000
• status[i] is either 0 or 1.
• 0 <= candies[i] <= 1000
• 0 <= keys[i].length <= n
• 0 <= contained_boxes[i].length <= n
• All values in keys[i] and contained_boxes[i] are unique and in the range [0, n - 1].
• 0 <= initial_boxes.length <= n
• Values in initial_boxes are unique and in the range [0, n - 1].