题目：
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。炸弹用一个下标从 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 <= 100bombs[i].length == 31 <= xi, yi, ri <= 105
思路：
方法1：暴力硬算
枚举每个点作为起点，通过广度优先搜索搜索其能引爆的气球，然后一路计算下去
这种暴力的巨大的问题就是，要进行n次广搜，每次广搜都要重新计算气球可达性，这里计算距离是最耗时的。所以我们要优化
方法2：转化为图可达性
我们要记录的只不过是两气球之间是否可达，所以计算一次距离，然后转化为可达性即可
可达性：r * r >= dx * dx + dy * dy 注意要用距离的平方，这样就能避免精度问题，同时减少计算量
判断连通性：如果 A 能引爆 B，我们就在图中记一条 A -> B，通过BFS求取以每个点为起点，能到达的所有节点。
代码：
class Solution {
public:
int bfs(int start, vector<vector<int>>& graph, int n) {
vector<bool> visited(n, false);
visited[start] = true;
int res = 1;
queue<int> que;
que.push(start);
while (!que.empty()) {
int top = que.front();
que.pop();
for (int i = 0; i < graph[top].size(); i++) {
if (!visited[graph[top][i]]) {
que.push(graph[top][i]);
visited[graph[top][i]] = true;
res++;
}
}
}
return res;
}
int maximumDetonation(vector<vector<int>>& bombs) {
// 图可达性问题
// 构建有向图（能到就是有一套边），最后判断从某个点出发最多能到几个点
int n = bombs.size();
// 领接表构建图
vector<vector<int>> graph(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long long dx = bombs[i][0] - bombs[j][0];
long long dy = bombs[i][1] - bombs[j][1];
if ((long long)bombs[i][2] * bombs[i][2] >= dx * dx + dy * dy) {
// i 可达 j
graph[i].push_back(j);
}
if ((long long)bombs[j][2] * bombs[j][2] >= dx * dx + dy * dy) {
// j 可达 i
graph[j].push_back(i);
}
}
}
// 求取从某一点出发可达的最多节点数
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, bfs(i, graph, n));
}
return ans;
}
};