2101. 引爆最多的炸弹

题目描述：

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

炸弹用一个下标从 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

---

解题分析及思路：

方法：深度优先搜索

思路：

利用深度优先搜索，搜索每个炸弹所能引爆的炸弹数目，如果能够引爆，则将能够引爆的炸弹数目加1，并再次以此方法搜索，直到没有可以引爆的炸弹为止。

例如： 炸弹：[[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]

计算出可以引爆的炸弹关系表，如下

[false  true  true  false false] 
[false  false false false false]
[false  true  false true  false]
[false  true  true  false true]
[false  false true  true  false]]

计算下标为0时：

1. 可以引爆下标为1和下标为2的炸弹，所以下标为0的炸弹可以引爆下标为1和下标为2的炸弹
2. 下标为1的炸弹不能引爆任何炸弹
3. 下标为2的炸弹可以引爆下标为3的炸弹
4. 下标为3的炸弹可以引爆下标为4的炸弹 所以最终可以引爆的炸弹数目为5（包含自己）

以此方法遍历所有炸弹，记录每个炸弹可以引爆的炸弹数目，取最大值。

func maximumDetonation(bombs [][]int) int {
	var maxCount int
	var n = len(bombs)
	var connects = make([][]bool, n)
	for i := 0; i < n; i++ {
		connects[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			if i != j {
				connects[i][j] = isRange(bombs[i], bombs[j])
			}
		}
	}
	for i := 0; i < n; i++ {
		var visited = make([]bool, n)
		maxCount = max(maxCount, dfs(bombs, visited, connects, i, n))
	}
	return maxCount
}

func dfs(bombs [][]int, visited []bool, connects [][]bool, index, n int) int {
	visited[index] = true
	var count int
	for i := 0; i < n; i++ {
		if !visited[i] && connects[index][i] {
			count += dfs(bombs, visited, connects, i, n)
		}
	}
	return count + 1
}

func isRange(num1, num2 []int) bool {
	return squ(num1[0]-num2[0])+squ(num1[1]-num2[1]) <= squ(num1[2])
}

func squ(num int) int {
	return num * num
}

func max(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}

复杂度：

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)

执行结果：

• 执行耗时:34 ms,击败了29.17% 的Go用户
• 内存消耗:5 MB,击败了62.50% 的Go用户