aboutsummaryrefslogtreecommitdiff
path: root/detonate_max_bombs.c
blob: ddf65c2203743b132462e4fcc96e6cd932e2c0f9 (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
85
86
87
// 2101. Detonate the Maximum Bombs
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * given a list of bombs. the range of a bomb is defined as the area where its
 * effect can be felt. this area is in the shape of a circle with the center as
 * the location of the bomb. the bombs are represented by a 0-indexed 2d integer
 * array 'bombs' where 'bombs[i] = [xi, yi, ri]'. 'xi' and 'yi' denote the x and
 * y coordinates of the location of the i'th bomb, whereas 'ri' denotes the
 * radius of its range. you may choose to detonate a single bomb. when a bomb is
 * detonated, it will detonate all the bombs that lie in its range. these bombs
 * will further detonate the bombs that lie in their ranges. given the list of
 * 'bombs', return the max number of bombs that can be detonated
 */

int maximumDetonation(int **bombs, int bombs_size, int *bombs_col_size) {
  bool *check = calloc(bombs_size, sizeof(bool));
  bool **attach = malloc(bombs_size * sizeof(bool *));
  for (int i = 0; i < bombs_size; i++)
    attach[i] = calloc(bombs_size, sizeof(bool));
  for (int i = 0; i < bombs_size; i++) {
    attach[i][i] = true;
    for (int j = i + 1; j < bombs_size; j++) {
      int x = abs(bombs[i][0] - bombs[j][0]);
      int y = abs(bombs[i][1] - bombs[j][1]);
      long long dis = (long long)x * x + (long long)y * y;
      if (dis <= (long long)bombs[i][2] * bombs[i][2])
        attach[i][j] = true;
      if (dis <= (long long)bombs[j][2] * bombs[j][2])
        attach[j][i] = true;
    }
  }
  int *stack1 = malloc(bombs_size * sizeof(int));
  int *stack2 = malloc(bombs_size * sizeof(int));
  int id1 = 0, id2 = 0, max = 1;
  for (int i = 0; i < bombs_size; i++) {
    check = calloc(bombs_size, sizeof(bool));
    int curr = 1;
    check[i] = true;
    stack1[id1] = i;
    id1++;
    while (id1 || id2) {
      if (id1) {
        for (int j = 0; j < id1; j++) {
          int p = stack1[j];
          for (int k = 0; k < bombs_size; k++) {
            if (attach[p][k] && !check[k]) {
              curr++;
              check[k] = true;
              stack2[id2] = k;
              id2++;
            }
          }
        }
        id1 = 0;
      } else {
        for (int j = 0; j < id2; j++) {
          int p = stack2[j];
          for (int k = 0; k < bombs_size; k++) {
            if (attach[p][k] && !check[k]) {
              curr++;
              check[k] = true;
              stack1[id1] = k;
              id1++;
            }
          }
        }
        id2 = 0;
      }
    }
    max = fmax(max, curr);
  }
  return max;
}

int main() {
  int b1[2][3] = {{2, 1, 3}, {6, 1, 4}}, bs1 = 2, *bcs1;
  int b2[2][5] = {{1, 1, 5}, {10, 10, 5}}, bs2 = 2, *bcs2;
  int b3[5][3] = {{1, 2, 3}, {2, 3, 1}, {3, 4, 2}, {4, 5, 3}, {5, 6, 4}},
      bs3 = 5, *bcs3;
  printf("%d\n", maximumDetonation(b1, bs1, bcs1)); // expect: 2
  printf("%d\n", maximumDetonation(b2, bs2, bcs2)); // expect: 1
  printf("%d\n", maximumDetonation(b3, bs3, bcs3)); // expect: 5
}