-
Notifications
You must be signed in to change notification settings - Fork 1
/
2101. Detonate the Maximum Bombs.java
46 lines (41 loc) · 1.48 KB
/
2101. Detonate the Maximum Bombs.java
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
class Solution {
public int maximumDetonation(int[][] bombs) {
Map<Integer, List<Integer>> graph = new HashMap<>();
int n = bombs.length;
// Build the graph
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
int xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
int xj = bombs[j][0], yj = bombs[j][1];
// Create a path from node i to node j, if bomb i detonates bomb j.
if ((long)ri * ri >= (long)(xi - xj) * (xi - xj) + (long)(yi - yj) * (yi - yj)) {
graph.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
}
}
}
int answer = 0;
for (int i = 0; i < n; i++) {
answer = Math.max(answer, dfs(i, graph));
}
return answer;
}
private int dfs(int i, Map<Integer, List<Integer>> graph) {
Stack<Integer> stack = new Stack<>();
Set<Integer> visited = new HashSet<>();
stack.push(i);
visited.add(i);
while (!stack.isEmpty()) {
int cur = stack.pop();
for (int neib : graph.getOrDefault(cur, new ArrayList<>())) {
if (!visited.contains(neib)) {
visited.add(neib);
stack.push(neib);
}
}
}
return visited.size();
}
}