aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_candies_from_boxes.c84
-rw-r--r--max_candies_from_boxes.py60
2 files changed, 144 insertions, 0 deletions
diff --git a/max_candies_from_boxes.c b/max_candies_from_boxes.c
new file mode 100644
index 0000000..03b4b5f
--- /dev/null
+++ b/max_candies_from_boxes.c
@@ -0,0 +1,84 @@
+// 1298. Maximum Candies You Can Get from Boxes
+#include "leetcode.h"
+
+/*
+ * you have 'n' boxes labeled from 0 to 'n - 1'. you are given four arrays:
+ * 'status', 'candies', 'keys', and 'containedBoxes' where 'status[i]' is 1 if
+ * the i'th box is open and 0 if the i'th box is closed. 'candies[i]' is the
+ * number of candies in the i'th box. 'keys[i]' is a list of the labels of the
+ * boxes that you can open after opening the i'th box. 'containedBoxes[i]' is a
+ * list of the boxes you found inside the i'th box. you are given an integer
+ * array 'initialBoxes' that contains the labels of the boxes you initially
+ * have. you can take all the candies in any open box and you can use the keys
+ * in it to open new boxes and you can also use the boxes you find in it. return
+ * the maximum number of candies you can get following the rules.
+ */
+
+int dfs(int box_idx, int *status, int statusSize, int *candies, int candiesSize,
+ int **keys, int keysSize, int *keysColSize, int **containedBoxes,
+ int containedBoxesSize, int *containedBoxesColSize, bool *accessible,
+ bool *vis, bool *have_key) {
+ int cnt = 0;
+ if (vis[box_idx] == 1 || !accessible[box_idx] ||
+ (!status[box_idx] && !have_key[box_idx]))
+ return 0;
+ cnt = candies[box_idx];
+ vis[box_idx] = 1;
+ for (int i = 0; i < keysColSize[box_idx]; i++) {
+ have_key[keys[box_idx][i]] = 1;
+ cnt += dfs(keys[box_idx][i], status, statusSize, candies, candiesSize, keys,
+ keysSize, keysColSize, containedBoxes, containedBoxesSize,
+ containedBoxesColSize, accessible, vis, have_key);
+ }
+ for (int i = 0; i < containedBoxesColSize[box_idx]; i++) {
+ accessible[containedBoxes[box_idx][i]] = 1;
+ cnt += dfs(containedBoxes[box_idx][i], status, statusSize, candies,
+ candiesSize, keys, keysSize, keysColSize, containedBoxes,
+ containedBoxesSize, containedBoxesColSize, accessible, vis,
+ have_key);
+ }
+ return cnt;
+}
+
+int maxCandies(int *status, int statusSize, int *candies, int candiesSize,
+ int **keys, int keysSize, int *keysColSize, int **containedBoxes,
+ int containedBoxesSize, int *containedBoxesColSize,
+ int *initialBoxes, int initialBoxesSize) {
+ bool *accessible = (bool *)calloc(statusSize, sizeof(bool));
+ bool *vis = (bool *)calloc(statusSize, sizeof(bool));
+ bool *have_key = (bool *)calloc(statusSize, sizeof(bool));
+ int ans = 0;
+ for (int i = 0; i < initialBoxesSize; i++) {
+ accessible[initialBoxes[i]] = true;
+ ans += dfs(initialBoxes[i], status, statusSize, candies, candiesSize, keys,
+ keysSize, keysColSize, containedBoxes, containedBoxesSize,
+ containedBoxesColSize, accessible, vis, have_key);
+ }
+ free(accessible);
+ free(vis);
+ free(have_key);
+ return ans;
+}
+
+int main() {
+ int s1[] = {1, 0, 1, 0}, c1[] = {7, 5, 4, 100}, k1i[4][1] = {{}, {}, {1}, {}},
+ cb1i[4][2] = {{1, 2}, {3}, {}, {}}, ib1[] = {0};
+ int s2[] = {1, 0, 0, 0, 0, 0}, c2[] = {1, 1, 1, 1, 1, 1},
+ k2i[6][5] = {{1, 2, 3, 4, 5}, {}, {}, {}, {}, {}},
+ cb2i[6][5] = {{1, 2, 3, 4, 5}, {}, {}, {}, {}, {}}, ib2[] = {0};
+ struct two_d_arr k1, k2, cb1, cb2;
+ two_d_arr_init(&k1, ARRAY_SIZE(k1i), ARRAY_SIZE(k1i[0]), k1i);
+ two_d_arr_init(&k2, ARRAY_SIZE(k2i), ARRAY_SIZE(k2i[0]), k2i);
+ two_d_arr_init(&cb1, ARRAY_SIZE(cb1i), ARRAY_SIZE(cb1i[0]), cb1i);
+ two_d_arr_init(&cb2, ARRAY_SIZE(cb2i), ARRAY_SIZE(cb2i[0]), cb2i);
+ printf("%d\n", maxCandies(s1, ARRAY_SIZE(s1), c1, ARRAY_SIZE(c1), k1.arr,
+ k1.row_size, k1.col_size, cb1.arr, cb1.row_size,
+ cb1.col_size, ib1, ARRAY_SIZE(ib1))); // expect: 16
+ printf("%d\n", maxCandies(s2, ARRAY_SIZE(s2), c2, ARRAY_SIZE(c2), k2.arr,
+ k2.row_size, k2.col_size, cb2.arr, cb2.row_size,
+ cb2.col_size, ib2, ARRAY_SIZE(ib2))); // expect: 6
+ two_d_arr_free(&k1);
+ two_d_arr_free(&k2);
+ two_d_arr_free(&cb1);
+ two_d_arr_free(&cb2);
+}
diff --git a/max_candies_from_boxes.py b/max_candies_from_boxes.py
new file mode 100644
index 0000000..2b1d1b3
--- /dev/null
+++ b/max_candies_from_boxes.py
@@ -0,0 +1,60 @@
+# 1298. Maximum Candies You Can Get from Boxes
+
+"""
+you have 'n' boxes labeled from 0 to 'n - 1'. you are given four arrays:
+'status', 'candies', 'keys', and 'containedBoxes' where 'status[i]' is 1 if
+the i'th box is open and 0 if the i'th box is closed. 'candies[i]' is the
+number of candies in the i'th box. 'keys[i]' is a list of the labels of the
+boxes that you can open after opening the i'th box. 'containedBoxes[i]' is a
+list of the boxes you found inside the i'th box. you are given an integer
+array 'initialBoxes' that contains the labels of the boxes you initially
+have. you can take all the candies in any open box and you can use the keys
+in it to open new boxes and you can also use the boxes you find in it. return
+the maximum number of candies you can get following the rules.
+"""
+
+
+class Solution(object):
+ def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
+ """
+ :type status: List[int]
+ :type candies: List[int]
+ :type keys: List[List[int]]
+ :type containedBoxes: List[List[int]]
+ :type initialBoxes: List[int]
+ :rtype: int
+ """
+ boxes = set(initialBoxes)
+ dfs = [i for i in boxes if status[i]]
+ for i in dfs:
+ for j in containedBoxes[i]:
+ boxes.add(j)
+ if status[j]:
+ dfs.append(j)
+ for j in keys[i]:
+ if status[j] == 0 and j in boxes:
+ dfs.append(j)
+ status[j] = 1
+ return sum(candies[i] for i in dfs)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxCandies(
+ status=[1, 0, 1, 0],
+ candies=[7, 5, 4, 100],
+ keys=[[], [], [1], []],
+ containedBoxes=[[1, 2], [3], [], []],
+ initialBoxes=[0],
+ )
+ )
+ print(
+ obj.maxCandies(
+ 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],
+ )
+ )