2101.maximun_detonation

. - 力扣（LeetCode）

参考了网友的解答

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