5936. 引爆最多的炸弹

题目地址(5936. 引爆最多的炸弹)

https://leetcode-cn.com/problems/detonate-the-maximum-bombs/

题目描述

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

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

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

给你数组 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 <= xi, yi, ri <= 105

前置知识

• BFS

公司

• 暂无

思路

刚开始的想法是计算图的最大联通分量，因此使用并查集就可以解决。

后来提交的时候发现有问题。这是因为题目限制了引爆关系指的是：某一个炸弹的引爆范围是否会引爆到其他炸弹的圆心，而不是相交就行。这提示了我们：炸弹 a 引爆炸弹 b 的情况下，炸弹 b 不一定能够引爆炸弹 a。

也就是说我们将炸弹看做是点，炸弹 a 如果能够引爆炸弹 b，那么就有一条从 a 到 b 的边。而并查集无法处理这种关系。

因此我们可以使用 BFS 来做。首先预处理出图，然后对于图中每一点 i 进行 BFS，然后在这 n 次 bfs 中将最大引爆炸弹数记录下来返回即可。

关键点

• BFS

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        d = collections.defaultdict(list)
        def overlap(i, j):
            x1, y1, r1 = bombs[i]
            x2, y2, r2 = bombs[j]
            return (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r1 ** 2
        for i in range(n):
            for j in range(i+1, n):
                if overlap(i, j):
                    d[i].append(j)
                if overlap(j, i):
                    d[j].append(i)
        ans = 1
        for i in range(n):
            q = collections.deque([i])
            vis = set()
            count = 0
            while q:
                cur = q.popleft()
                if cur in vis: continue
                vis.add(cur)
                count += 1
                for neibor in d[cur]:
                    q.append(neibor)
            ans = max(ans, count)
        return ans

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^3)$. 其中建图部分时间复杂度为 $O(n^2)$，。并且由于每个点的出度最多为 n，因此对于每一个点 i BFS 的时间复杂度为 $n^2$，由于一共有 n 个点，因此总时间复杂度为 $O(n^3)$。

• 空间复杂度：$O(n^3)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。