aboutsummaryrefslogtreecommitdiff
path: root/max_candies_from_boxes.c
blob: 03b4b5f7881e24c30400fff95dcf04a24d9a5628 (plain)
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);
}