Sponsored
Sponsored
Represent each bomb as a node in a graph. An edge exists from bomb i to bomb j if bomb i can detonate bomb j. The goal is to start from each bomb and use BFS to find how many bombs can be detonated. Return the maximum number of detonatable bombs starting from any single bomb.
Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs.
Space Complexity: O(n), for storing the adjacency list of the graph and the visited list.
1import java.util.*;
2
3class Solution {
4 private boolean canDetonate(int[] bomb1, int[] bomb2) {
5 long x1 = bomb1[0], y1 = bomb1[1], r1 = bomb1[2];
6 long x2 = bomb2[0], y2 = bomb2[1];
7 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1;
8 }
9
10 public int maximumDetonation(int[][] bombs) {
11 int n = bombs.length;
12 List<Integer>[] graph = new ArrayList[n];
13 for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
14
15 for (int i = 0; i < n; i++) {
16 for (int j = 0; j < n; j++) {
17 if (i != j && canDetonate(bombs[i], bombs[j])) {
18 graph[i].add(j);
19 }
20 }
21 }
22
23 int maxDetonated = 0;
24 for (int i = 0; i < n; i++) {
25 boolean[] visited = new boolean[n];
26 Queue<Integer> queue = new LinkedList<>();
27 queue.offer(i);
28 visited[i] = true;
29 int count = 0;
30
31 while (!queue.isEmpty()) {
32 int current = queue.poll();
33 count++;
34 for (int neighbor : graph[current]) {
35 if (!visited[neighbor]) {
36 visited[neighbor] = true;
37 queue.offer(neighbor);
38 }
39 }
40 }
41 maxDetonated = Math.max(maxDetonated, count);
42 }
43
44 return maxDetonated;
45 }
46}Similar to the Python implementation, this Java version constructs an adjacency list for the graph of bombs and uses BFS to search through the graph from each possible starting bomb. The maximum number of detonatable bombs is computed and returned.
Another approach to solve this problem is by using a DFS traversal instead of BFS. We use a similar graph representation where each bomb is a node and an edge exists if one bomb can detonate another. The maximum number of bombs that can be reached starting from each node (bomb) is determined using DFS.
Time Complexity: O(n^2) for constructing the graph and performing DFS traversals.
Space Complexity: O(n) used in the recursion stack and the visited vector.
1#include <vector>
2#include <cmath>
3using namespace std;
4
5bool canDetonate(const vector<int>& bomb1, const vector<int>& bomb2) {
long long x1 = bomb1[0], y1 = bomb1[1], r1 = bomb1[2];
long long x2 = bomb2[0], y2 = bomb2[1];
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1;
}
void dfs(const vector<vector<int>>& graph, vector<bool>& visited, int index, int& count) {
visited[index] = true;
count++;
for (int neighbor : graph[index]) {
if (!visited[neighbor]) {
dfs(graph, visited, neighbor, count);
}
}
}
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
vector<vector<int>> graph(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && canDetonate(bombs[i], bombs[j])) {
graph[i].push_back(j);
}
}
}
int maxDetonated = 0;
for (int i = 0; i < n; i++) {
vector<bool> visited(n, false);
int count = 0;
dfs(graph, visited, i, count);
maxDetonated = max(maxDetonated, count);
}
return maxDetonated;
}This C++ implementation uses DFS to explore each detonation starting from every bomb and computes the maximum possible detonations. It uses a recursive function to delve deeper into the graph from each bomb until all reachable bombs are visited starting from a given bomb.