参考了网友的解答
from typing import List
class Solution:
# 是否能引爆，当r大于等于两点坐标的距离时，可以引爆
def is_bomb(self, x1, x2, y1, y2, r):
return r >= ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
# 计算i炸弹开始引爆的最长路
def relation_bomb_count(self, relation, i, n):
count = 0
is_bombs = [False for _ in range(n)]
is_bombs[i] = True
# 爆破队列
bombs_queue = [i]
while bombs_queue:
node = bombs_queue.pop(0)
count += 1
# 若是当前炸弹爆炸触发其他未爆炸的炸弹爆炸，那么加入爆破队列
for r_bomb in relation[node]:
if not is_bombs[r_bomb]:
bombs_queue.append(r_bomb)
# 加入就需要将炸弹设置为引爆，不然当a触发b,c爆炸时，b也会触发c时，c就爆炸了两次了
is_bombs[r_bomb] = True
return count
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
# 建立关系图,每个炸弹会触发其他炸弹爆炸的关系
relation_bomb = [[] for _ in range(n)]
for i, (x1, y1, r) in enumerate(bombs):
for j, (x2, y2, _) in enumerate(bombs):
if i != j and self.is_bomb(x1, x2, y1, y2, r):
relation_bomb[i].append(j)
# 定义引爆最长路
max_b = 1
# 枚举所有节点作为引爆点，计算引爆最长路
for i in range(n):
max_b = max(max_b, self.relation_bomb_count(relation_bomb, i, n))
return max_b