引爆最多的炸弹

难度: Medium

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [x_i, y_i, r_i] 。x_i 和 y_i 表示第 i 个炸弹的 X 和 Y 坐标，r_i 表示爆炸范围的半径。

你需要选择引爆一个炸弹。当这个炸弹被引爆时，所有在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆一个炸弹的前提下，最多能引爆的炸弹数目。

示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。

提示：

1 <= bombs.length <= 100
bombs[i].length == 3
1 <= x_i, y_i, r_i <= 10⁵

Submission

运行时间: 110 ms

内存: 16.6 MB

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        ##给定一个有向图（可能存在环），求目标起点，使得能够到达的节点数目最多
        n=len(bombs)
        nxt=[[] for _ in range(n)]
        for i in range(n):
            x1,y1,r1=bombs[i]
            for j in range(i):
                x2,y2,r2=bombs[j]
                d2=(x1-x2)**2+(y1-y2)**2
                if d2<=r1**2:
                    nxt[i].append(j)
                if d2<=r2**2:
                    nxt[j].append(i)
                
        def forward(x,vis):
            vis.add(x)
            for y in nxt[x]:
                if y not in vis:
                    forward(y,vis)
        ans=1
        vis=set()
        for i in range(n):
            if i in vis:continue
            newVis=set()
            forward(i,newVis)
            ans=max(ans,len(newVis))
            vis |=newVis
        return ans

Explain

这道题目可以视为图的问题，其中每个炸弹是一个节点，如果一个炸弹可以引爆另一个炸弹，则在这两个炸弹之间存在一条有向边。首先，我们通过计算两个炸弹之间的距离与半径比较，来构建这个有向图的邻接表。接着，从每个节点开始，使用深度优先搜索（DFS）来探索从该节点出发能够到达多少其他节点，即引爆多少其他炸弹。最后，返回能够引爆最多炸弹的数量。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        nxt = [[] for _ in range(n)]
        for i in range(n):
            x1, y1, r1 = bombs[i]
            for j in range(n):
                if i != j:
                    x2, y2, r2 = bombs[j]
                    d2 = (x1 - x2)**2 + (y1 - y2)**2
                    if d2 <= r1**2:
                        nxt[i].append(j)

        def forward(x, vis):
            vis.add(x)
            for y in nxt[x]:
                if y not in vis:
                    forward(y, vis)

        ans = 1
        vis = set()
        for i in range(n):
            if i in vis:
                continue
            newVis = set()
            forward(i, newVis)
            ans = max(ans, len(newVis))
            vis |= newVis
        return ans

Explore

要确定一个炸弹能否引爆另一个炸弹，我们需要计算两个炸弹中心点之间的欧几里得距离是否小于或等于引爆炸弹的半径。具体来说，如果炸弹A的坐标是(x1, y1)且半径为r1，炸弹B的坐标是(x2, y2)，则两者之间的距离平方d2计算为(x1 - x2)^2 + (y1 - y2)^2。如果d2小于或等于r1的平方，那么炸弹A可以引爆炸弹B，因此在A和B之间存在有向边。

在构建邻接表时，使用列表的原因是因为列表在这种场景下提供了简单且高效的访问方式。由于每个炸弹可能引爆的炸弹数量不一定相同，使用列表可以直接按索引顺序存储和访问那些可以被引爆的炸弹，而不需要处理额外的键存在性检查或去重操作，这在哈希表或集合中是必需的。此外，列表在添加元素时通常比集合有更好的时间效率，特别是在元素数量不大时。

在深度优先搜索（DFS）过程中，`vis` 集合用于记录已经访问（引爆）过的炸弹节点，确保每个炸弹在搜索过程中只被引爆一次。当DFS访问一个炸弹时，会将其添加到`vis`集合中，之后如果再次遇到这个炸弹，会通过检查`vis`集合来跳过，从而避免重复引爆。这样可以有效防止无限循环和不必要的重复计算，确保算法的效率和正确性。