Maximum Candies You Can Get from Boxes

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


Intuition

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.

Solution


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]:
                    continue
                if (has_key[child] or status[child]) and can_visited[child]:
                    visited[child] = True
                    queue.append(child)
        
        total_candies = 0
        for i in range(n):
            if visited[i]:
                total_candies += candies[i]
        return total_candies