use std::collections::{HashMap, VecDeque};
use std::cmp::max;
impl Solution {
pub fn maximum_detonation(bombs: Vec<Vec<i32>>) -> i32 {
let n = bombs.len();
// 判断炸弹 u 能否引爆炸弹 v
let is_connected = |u: usize, v: usize| -> bool {
let dx = (bombs[u][0] - bombs[v][0]) as i64;
let dy = (bombs[u][1] - bombs[v][1]) as i64;
(bombs[u][2] as i64) * (bombs[u][2] as i64) >= (dx * dx + dy * dy)
};
// 维护引爆关系有向图
let mut edges: HashMap<usize, Vec<usize>> = HashMap::new();
for i in 0..n {
for j in 0..n {
if i != j && is_connected(i, j) {
edges.entry(i).or_insert(Vec::new()).push(j);
}
}
}
let mut res = 0; // 最多引爆数量
for i in 0..n {
// 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值
let mut visited = vec![0; n];
let mut cnt = 1;
let mut q = VecDeque::new();
q.push_back(i);
visited[i] = 1;
while let Some(cidx) = q.pop_front() {
for &nidx in edges.get(&cidx).unwrap_or(&vec![]) {
if visited[nidx] == 1 {
continue;
}
cnt += 1;
q.push_back(nidx);
visited[nidx] = 1;
}
}
res = max(res, cnt);
}
res
}
}
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
# 判断炸弹 u 能否引爆炸弹 v
def isConnected(u: int, v: int) -> bool:
dx = bombs[u][0] - bombs[v][0]
dy = bombs[u][1] - bombs[v][1]
return bombs[u][2] ** 2 >= dx ** 2 + dy ** 2
# 维护引爆关系有向图
edges = defaultdict(list)
for i in range(n):
for j in range(n):
if i != j and isConnected(i, j):
edges[i].append(j)
res = 0 # 最多引爆数量
for i in range(n):
# 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值
visited = [False] * n
cnt = 1
q = deque([i])
visited[i] = True
while q:
cidx = q.popleft()
for nidx in edges[cidx]:
if visited[nidx]:
continue
cnt += 1
q.append(nidx)
visited[nidx] = True
res = max(res, cnt)
return res
class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
// 判断炸弹 u 能否引爆炸弹 v
auto isConnected = [&](int u, int v) -> bool {
long long dx = bombs[u][0] - bombs[v][0];
long long dy = bombs[u][1] - bombs[v][1];
return (long long)bombs[u][2] * bombs[u][2] >= dx * dx + dy * dy;
};
// 维护引爆关系有向图
unordered_map<int, vector<int>> edges;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && isConnected(i, j)) {
edges[i].push_back(j);
}
}
}
int res = 0; // 最多引爆数量
for (int i = 0; i < n; ++i) {
// 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值
vector<int> visited(n);
int cnt = 1;
queue<int> q;
q.push(i);
visited[i] = 1;
while (!q.empty()) {
int cidx = q.front();
q.pop();
for (const int nidx: edges[cidx]) {
if (visited[nidx]) {
continue;
}
++cnt;
q.push(nidx);
visited[nidx] = 1;
}
}
res = max(res, cnt);
}
return res;
}
};
func maximumDetonation(bombs [][]int) (ans int) {
n := len(bombs)
g := make([][]int, n)
for i, p := range bombs {
for j, q := range bombs {
if j != i && (q[0]-p[0])*(q[0]-p[0])+(q[1]-p[1])*(q[1]-p[1]) <= p[2]*p[2] {
g[i] = append(g[i], j) // 有向图，从 i 向 j 连边，表示引爆 i 可以引爆 j
}
}
}
for i := range g { // 暴力枚举所有起点，跑 DFS 看能访问到多少节点
vis := make([]bool, n)
cnt := 0
var dfs func(int)
dfs = func(v int) {
vis[v] = true
cnt++
for _, w := range g[v] {
if !vis[w] {
dfs(w)
}
}
}
dfs(i)
if cnt > ans {
ans = cnt
}
}
return
}
