Q:

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

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

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

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

示例 1：

示例 2：

示例 3：

思路

1. 首先要构建一个拓扑关系图，每个炸弹找到其爆炸范围内包含的炸弹。

1. 对图中每个节点进行DFS遍历， 看看起始引爆该炸弹会连带多少个炸弹引爆。

1. DFS过程中记录Max值

注意： 需要一个Path来记录路径，DFS时重复了。

Code

Prev

2766. 重新放置石块

Next

Git相关问题记录