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.
1from collections import deque
2
3def can_detonate(bomb1, bomb2):
4 x1, y1, r1 = bomb1
5 x2, y2, _ = bomb2
6 return (x1 - x2)**2 + (y1 - y2)**2 <= r1**2
7
8
9def maximum_detonation(bombs):
10 n = len(bombs)
11 graph = [[] for _ in range(n)]
12
13 # Build graph
14 for i in range(n):
15 for j in range(n):
16 if i != j and can_detonate(bombs[i], bombs[j]):
17 graph[i].append(j)
18
19 def bfs(start):
20 visited = [False] * n
21 queue = deque([start])
22 visited[start] = True
23 count = 0
24
25 while queue:
26 current = queue.popleft()
27 count += 1
28 for neighbor in graph[current]:
29 if not visited[neighbor]:
30 visited[neighbor] = True
31 queue.append(neighbor)
32
33 return count
34
35 max_detonated = 0
36 for i in range(n):
37 max_detonated = max(max_detonated, bfs(i))
38
39 return max_detonatedThis code constructs a graph with each bomb as a node and checks if a bomb can detonate another based on their respective ranges. BFS is used from each bomb to determine the total number of bombs that can be detonated, and the maximum among all is 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.
1function canDetonate(bomb1, bomb2) {
2
This JavaScript solution uses a DFS recursive approach to enumerate all bombs that can be detonated starting from one bomb. It iterates over each bomb, employs DFS to count reachable detonations, and stores the maximum value observed.