目标
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 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 <= 10^5
思路
坐标平面上有一些炸弹，并且已知炸弹的爆炸范围。现在可以选择引爆其中的一颗炸弹，被引爆炸弹的爆炸范围内的其它炸弹也会被引爆，问最多可以引爆的炸弹数量。
我们可以将问题转换为有向图，一枚炸弹能够波及到的其它炸弹认为是连通的，然后遍历每一枚炸弹，求出连通炸弹数量最多的个数即可。
那么如何建立这个有向图呢？固定一个，依次与其余的节点比较，时间复杂度为O(n^2)，炸弹最多100个，应该可行。
实现过程中需要判断爆炸范围内的是否存在其它炸弹，可以使用炸弹坐标（圆心）之间的距离与各自的引爆半径相比较。这里需要注意防止数据溢出，另外还有一个小技巧，比较 sqrt(dx^2 + dy^2) 与 半径 r 的效率没有 dx^2 + dy^2 与 r^2 高。
网友最快的题解使用的是 Floyd 算法。// todo
代码
/**
* @date 2024-07-22 9:24
*/
public class MaximumDetonation2101 {
public int maximumDetonation_v1(int[][] bombs) {
int n = bombs.length;
List<Integer>[] g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
int ix = bombs[i][0];
int iy = bombs[i][1];
long ir = bombs[i][2];
for (int j = i + 1; j < n; j++) {
int jx = bombs[j][0];
int jy = bombs[j][1];
long jr = bombs[j][2];
// 防止溢出
long diffx = ix - jx;
long diffy = iy - jy;
long dist = diffx * diffx + diffy * diffy;
if (ir * ir >= dist) {
g[i].add(j);
}
if (jr * jr >= dist) {
g[j].add(i);
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
boolean[] visited = new boolean[n];
res = Math.max(res, dfs(i, g, visited));
}
return res;
}
int dfs(int root, List<Integer>[] g, boolean[] visited) {
visited[root] = true;
int res = 1;
for (Integer next : g[root]) {
if (visited[next]) {
continue;
}
res += dfs(next, g, visited);
}
return res;
}
}
性能
图中至多有 n^2 条边，dfs的时间复杂度是O(n^2)，然后再遍历n个起点，时间复杂度为O(n^3)。
