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_detonated

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;
}