跳转至

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

解法

方法一：BFS

枚举每个炸弹 k 作为起始引爆点，BFS 搜索能影响到的所有炸弹的数量，取其最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        def check(i, j):
            if i == j:
                return False
            x, y = bombs[i][0] - bombs[j][0], bombs[i][1] - bombs[j][1]
            r = bombs[i][2]
            return r * r >= x * x + y * y

        g = defaultdict(list)
        n = len(bombs)
        for i in range(n):
            for j in range(n):
                if check(i, j):
                    g[i].append(j)
        ans = 0
        for k in range(n):
            q = deque([k])
            vis = [False] * n
            vis[k] = True
            cnt = 0
            while q:
                i = q.popleft()
                cnt += 1
                for j in g[i]:
                    if not vis[j]:
                        vis[j] = True
                        q.append(j)
            ans = max(ans, cnt)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    private int[][] bombs;

    public int maximumDetonation(int[][] bombs) {
        this.bombs = bombs;
        int n = bombs.length;
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                g[i][j] = check(i, j);
            }
        }
        int ans = 0;
        for (int k = 0; k < n; ++k) {
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(k);
            boolean[] vis = new boolean[n];
            vis[k] = true;
            int cnt = 0;
            while (!q.isEmpty()) {
                int i = q.poll();
                ++cnt;
                for (int j = 0; j < n; ++j) {
                    if (g[i][j] && !vis[j]) {
                        vis[j] = true;
                        q.offer(j);
                    }
                }
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }

    private boolean check(int i, int j) {
        if (i == j) {
            return false;
        }
        long x = bombs[i][0] - bombs[j][0];
        long y = bombs[i][1] - bombs[j][1];
        long r = bombs[i][2];
        return r * r >= x * x + y * y;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        vector<vector<bool>> g(n, vector<bool>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] = check(i, j, bombs);
        int ans = 0;
        for (int k = 0; k < n; ++k) {
            queue<int> q{{k}};
            vector<bool> vis(n);
            vis[k] = true;
            int cnt = 0;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                ++cnt;
                for (int j = 0; j < n; ++j) {
                    if (g[i][j] && !vis[j]) {
                        vis[j] = true;
                        q.push(j);
                    }
                }
            }
            ans = max(ans, cnt);
        }
        return ans;
    }

    bool check(int i, int j, vector<vector<int>>& bombs) {
        if (i == j) return false;
        long long x = bombs[i][0] - bombs[j][0];
        long long y = bombs[i][1] - bombs[j][1];
        long long r = bombs[i][2];
        return r * r >= x * x + y * y;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func maximumDetonation(bombs [][]int) int {
    check := func(i, j int) bool {
        if i == j {
            return false
        }
        x, y := bombs[i][0]-bombs[j][0], bombs[i][1]-bombs[j][1]
        r := bombs[i][2]
        return r*r >= x*x+y*y
    }
    n := len(bombs)
    g := make([][]bool, n)
    for i := range g {
        g[i] = make([]bool, n)
        for j := range g[i] {
            g[i][j] = check(i, j)
        }
    }

    ans := 0
    for k := 0; k < n; k++ {
        q := []int{k}
        vis := make([]bool, n)
        vis[k] = true
        cnt := 0
        for len(q) > 0 {
            i := q[0]
            q = q[1:]
            cnt++
            for j := 0; j < n; j++ {
                if g[i][j] && !vis[j] {
                    vis[j] = true
                    q = append(q, j)
                }
            }
        }
        ans = max(ans, cnt)
    }
    return ans
}

评论