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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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);
}
|