// 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 = two_d_arr_init(ARRAY_SIZE(k1i), ARRAY_SIZE(k1i[0]), k1i); struct two_d_arr *k2 = two_d_arr_init(ARRAY_SIZE(k2i), ARRAY_SIZE(k2i[0]), k2i); struct two_d_arr *cb1 = two_d_arr_init(ARRAY_SIZE(cb1i), ARRAY_SIZE(cb1i[0]), cb1i); struct two_d_arr *cb2 = two_d_arr_init(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); }