526互联

[LeetCode] 2101. Detonate the Maximum Bombs

发布时间 2023-06-03 02:48:40作者: CNoodle

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.

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 ith bomb, whereas ri denotes the radius of its range.

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.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

Constraints:

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= xi, yi, ri <= 105

引爆最多的炸弹。

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/detonate-the-maximum-bombs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道图论 + 几何的题，我这里提供一个 BFS 的思路。我需要一个额外的二维数组 accessible 去记录炸弹 A 是否能引爆炸弹 B。两两遍历 input 给的所有炸弹之后把结果记录在 accessible 数组中。

再次遍历所有的炸弹，假设我们引爆当前的炸弹，然后去找哪些还未访问过的炸弹是可以被当前这个炸弹引爆的。比较一下看看引爆哪个炸弹获得的收益最大 - 能同时引爆更多的炸弹。

时间O(n^2)

空间O(n^2)

Java实现

 1 class Solution {
 2     public int maximumDetonation(int[][] bombs) {
 3         int n = bombs.length;
 4         boolean[][] accessible = new boolean[n][n];
 5         for (int i = 0; i < n; i++) {
 6             for (int j = i + 1; j < n; j++) {
 7                 int a = bombs[i][0] - bombs[j][0];
 8                 int b = bombs[i][1] - bombs[j][1];
 9                 long aabb = 1L * a * a + 1L * b * b;
10                 if (1L * bombs[i][2] * bombs[i][2] >= aabb) {
11                     accessible[i][j] = true;
12                 }
13                 if (1L * bombs[j][2] * bombs[j][2] >= aabb) {
14                     accessible[j][i] = true;
15                 }
16             }
17         }
18 
19         int max = 0;
20         for (int i = 0; i < n; i++) {
21             Queue<Integer> queue = new LinkedList<>();
22             boolean[] visited = new boolean[n];
23             int count = 0;
24 
25             queue.offer(i);
26             visited[i] = true;
27             while (!queue.isEmpty()) {
28                 int cur = queue.poll();
29                 count++;
30                 for (int j = 0; j < n; j++) {
31                     if (!visited[j] && accessible[cur][j]) {
32                         queue.offer(j);
33                         visited[j] = true;
34                     }
35                 }
36             }
37             max = Math.max(max, count);
38         }
39         return max;
40     }
41 }

 

LeetCode 题目总结