Maximum Candies You Can Get from Boxes

Problem Id: 1298 Difficulty: Hard Tag: Breadth-first Search


From the description, we could visit a box if we have the box, and we have key to the box or the box is open.

So I use has_key, can_visited and the given status to mark the status of a box. Once any status of a box is updated, we could check other status of the box to see if we could open it. If it is, we can add it to the queue.

This problem is interesting, because it is not actually a graph problem. But, we could use BFS to solve it.


from collections import deque

class Solution:
    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        n = len(status)
        visited = [False] * n
        has_key = [False] * n
        can_visited = [False] * n
        status = [bool(i) for i in status]
        queue = deque(initialBoxes)
        for box in initialBoxes:
            visited[box] = True

        while queue:
            current = queue.popleft()
            for child in keys[current]:
                has_key[child] = True
            for child in containedBoxes[current]:
                can_visited[child] = True

            for child in keys[current] + containedBoxes[current]:
                if visited[child]:
                if (has_key[child] or status[child]) and can_visited[child]:
                    visited[child] = True
        total_candies = 0
        for i in range(n):
            if visited[i]:
                total_candies += candies[i]
        return total_candies