摘要: 难点在于正确建图
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
各位好,今天我们来看一个通过建图将问题转化为图上的搜索问题,难点在于正确建图。
题目
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0 开始的二维整数数组 bombs 表示,其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标,ri 表示爆炸范围的 半径 。
你需要选择引爆 一个 炸弹。当这个炸弹被引爆时,所有 在它爆炸范围内的炸弹都会被引爆,这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组 bombs ,请你返回在引爆 一个 炸弹的前提下,最多 能引爆的炸弹数目。
提示:
1 | 1 <= bombs.length <= 100 |
示例 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 个炸弹被引爆。
题解
算法: 建图
将每个圆视为一个节点。对于两个节点 i,j,如果 j 在 i 的爆炸范围内,即引爆 i 会进一步引爆 j,则链接有向边 i→j;类似地,如果 i 在 j 的爆炸范围,则链接有向边 j→i。
然后枚举图中的每个节点,将其作为起点在图中 DFS,可以搜索到的节点个数就是一个候选答案。
关于这个图有两个需要注意的地方,一个是该图是一个有向图,引爆 i 可以进一步引爆 j 不代表引爆 j 可以进一步引爆 i,因此用并查集是不行的。另一个是图的边数最坏情况是 O(N2),因此一次 DFS 的最坏时间复杂度为 O(N2)。
代码 (Python)
1 | class Solution: |