# 1298. Maximum Candies You Can Get from Boxes¶

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: int maxCandies(vector& status, vector& candies, vector>& keys, vector>& containedBoxes, vector& initialBoxes) { int ans = 0; queue q; vector reachedClosedBoxes(status.size()); auto pushBoxesIfPossible = [&status, &q, &reachedClosedBoxes](const vector& boxes) { for (const int box : boxes) if (status[box]) q.push(box); else reachedClosedBoxes[box] = true; }; pushBoxesIfPossible(initialBoxes); while (!q.empty()) { const int currBox = q.front(); q.pop(); // Add the candies. ans += candies[currBox]; // Push reachedClosedBoxes by key obtained in this turn and change // their statuses. for (const int key : keys[currBox]) { if (!status[key] && reachedClosedBoxes[key]) q.push(key); status[key] = 1; // boxes[key] is now open. } // Push the boxes contained in currBox. pushBoxesIfPossible(containedBoxes[currBox]); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) { int ans = 0; Queue q = new ArrayDeque<>(); boolean[] reachedClosedBoxes = new boolean[status.length]; pushBoxesIfPossible(initialBoxes, status, q, reachedClosedBoxes); while (!q.isEmpty()) { final int currBox = q.poll(); // Add the candies. ans += candies[currBox]; // Push reachedClosedBoxes by key obtained in this turn and change // their statuses. for (final int key : keys[currBox]) { if (status[key] == 0 && reachedClosedBoxes[key]) q.offer(key); status[key] = 1; // boxes[key] is now open. } // Push the boxes contained in currBox. pushBoxesIfPossible(containedBoxes[currBox], status, q, reachedClosedBoxes); } return ans; } private void pushBoxesIfPossible(int[] boxes, int[] status, Queue q, boolean[] reachedClosedBoxes) { for (final int box : boxes) if (status[box] == 1) q.offer(box); else reachedClosedBoxes[box] = true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int: ans = 0 q = collections.deque() reachedClosedBoxes = [0] * len(status) def pushBoxesIfPossible(boxes: List[int]) -> None: for box in boxes: if status[box]: q.append(box) else: reachedClosedBoxes[box] = True pushBoxesIfPossible(initialBoxes) while q: currBox = q.popleft() # Add the candies. ans += candies[currBox] # Push reachedClosedBoxes by key obtained in this turn and change # their statuses. for key in keys[currBox]: if not status[key] and reachedClosedBoxes[key]: q.append(key) status[key] = 1 # boxes[key] is now open # Push the boxes contained in currBox. pushBoxesIfPossible(containedBoxes[currBox]) return ans