2101. Detonate the Maximum Bombs Medium

1/**
2 * [2101] Detonate the Maximum Bombs
3 *
4 * You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.
5 * The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the i^th bomb, whereas ri denotes the radius of its range.
6 * You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.
7 * Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-3.png" style="width: 300px; height: 300px;" />
11 * Input: bombs = [[2,1,3],[6,1,4]]
12 * Output: 2
13 * Explanation:
14 * The above figure shows the positions and ranges of the 2 bombs.
15 * If we detonate the left bomb, the right bomb will not be affected.
16 * But if we detonate the right bomb, both bombs will be detonated.
17 * So the maximum bombs that can be detonated is max(1, 2) = 2.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-2.png" style="width: 300px; height: 300px;" />
21 * Input: bombs = [[1,1,5],[10,10,5]]
22 * Output: 1
23 * Explanation:
24 * Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.
25 * 
26 * Example 3:
27 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/07/desmos-eg1.png" style="width: 300px; height: 300px;" />
28 * Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
29 * Output: 5
30 * Explanation:
31 * The best bomb to detonate is bomb 0 because:
32 * - Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
33 * - Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
34 * - Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
35 * Thus all 5 bombs are detonated.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= bombs.length <= 100
41 * 	bombs[i].length == 3
42 * 	1 <= xi, yi, ri <= 10^5
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/detonate-the-maximum-bombs/
48// discuss: https://leetcode.com/problems/detonate-the-maximum-bombs/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn maximum_detonation(bombs: Vec<Vec<i32>>) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2101() {
66    }
67}
68