Medium

题目描述

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

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri]。xi 和 yi 表示第 i 个炸弹的 X 坐标和 Y 坐标，ri 表示爆炸范围的半径。

你可以选择引爆 一个 炸弹。当一个炸弹被引爆时，它会引爆爆炸范围内的所有炸弹。这些炸弹会进一步引爆它们爆炸范围内的炸弹。

给你炸弹列表，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

示例 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 <= 10^5

解题思路

这是一个典型的图论问题。我们需要建立炸弹之间的引爆关系图，然后从每个炸弹开始进行搜索，找出能引爆的最大数量。

解题思路：

  1. 建图阶段：遍历所有炸弹对，判断炸弹 i 是否能引爆炸弹 j。如果炸弹 i 到炸弹 j 的距离小于等于炸弹 i 的爆炸半径，则可以引爆。注意这是有向图，因为炸弹 i 能引爆炸弹 j 不代表炸弹 j 能引爆炸弹 i。

  2. 距离计算：两点间距离使用欧几里得距离公式 sqrt((x1-x2)² + (y1-y2)²)。为避免浮点数精度问题，我们比较距离的平方。

  3. 搜索阶段：对每个炸弹作为起始点，使用 DFS 或 BFS 遍历所有能够到达的炸弹，统计数量。

  4. 优化细节：使用邻接表存储图结构，用 visited 数组避免重复访问，记录每次搜索的最大值。

时间复杂度主要由建图的 O(n²) 和 n 次 DFS 的 O(n²) 组成，总体为 O(n²)。由于 n ≤ 100，这个复杂度是可接受的。

代码实现

class Solution {
public:
    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 = 0; j < n; j++) {
                if (i != j) {
                    long long dx = bombs[i][0] - bombs[j][0];
                    long long dy = bombs[i][1] - bombs[j][1];
                    long long distSq = dx * dx + dy * dy;
                    long long radiusSq = (long long)bombs[i][2] * bombs[i][2];
                    
                    if (distSq <= radiusSq) {
                        graph[i].push_back(j);
                    }
                }
            }
        }
        
        int maxBombs = 0;
        
        // 对每个炸弹进行DFS
        for (int i = 0; i < n; i++) {
            vector<bool> visited(n, false);
            int count = dfs(i, graph, visited);
            maxBombs = max(maxBombs, count);
        }
        
        return maxBombs;
    }
    
private:
    int dfs(int bomb, vector<vector<int>>& graph, vector<bool>& visited) {
        visited[bomb] = true;
        int count = 1;
        
        for (int next : graph[bomb]) {
            if (!visited[next]) {
                count += dfs(next, graph, visited);
            }
        }
        
        return count;
    }
};

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        graph = [[] for _ in range(n)]
        
        # 建图
        for i in range(n):
            for j in range(n):
                if i != j:
                    dx = bombs[i][0] - bombs[j][0]
                    dy = bombs[i][1] - bombs[j][1]
                    dist_sq = dx * dx + dy * dy
                    radius_sq = bombs[i][2] * bombs[i][2]
                    
                    if dist_sq <= radius_sq:
                        graph[i].append(j)
        
        def dfs(bomb, visited):
            visited[bomb] = True
            count = 1
            
            for next_bomb in graph[bomb]:
                if not visited[next_bomb]:
                    count += dfs(next_bomb, visited)
            
            return count
        
        max_bombs = 0
        
        # 对每个炸弹进行DFS
        for i in range(n):
            visited = [False] * n
            count = dfs(i, visited)
            max_bombs = max(max_bombs, count)
        
        return max_bombs

public class Solution {
    public int MaximumDetonation(int[][] bombs) {
        int n = bombs.Length;
        var graph = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 建图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    long dx = bombs[i][0] - bombs[j][0];
                    long dy = bombs[i][1] - bombs[j][1];
                    long distSq = dx * dx + dy * dy;
                    long radiusSq = (long)bombs[i][2] * bombs[i][2];
                    
                    if (distSq <= radiusSq) {
                        graph[i].Add(j);
                    }
                }
            }
        }
        
        int maxBombs = 0;
        
        // 对每个炸弹进行DFS
        for (int i = 0; i < n; i++) {
            bool[] visited = new bool[n];
            int count = DFS(i, graph, visited);
            maxBombs = Math.Max(maxBombs, count);
        }
        
        return maxBombs;
    }
    
    private int DFS(int bomb, List<int>[] graph, bool[] visited) {
        visited[bomb] = true;
        int count = 1;
        
        foreach (int next in graph[bomb]) {
            if (!visited[next]) {
                count += DFS(next, graph, visited);
            }
        }
        
        return count;
    }
}

var maximumDetonation = function(bombs) {
    const n = bombs.length;
    const graph = Array.from({length: n}, () => []);
    
    // 建图
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                const dx = bombs[i][0] - bombs[j][0];
                const dy = bombs[i][1] - bombs[j][1];
                const distSq = dx * dx + dy * dy;
                const radiusSq = bombs[i][2] * bombs[i][2];
                
                if (distSq <= radiusSq) {
                    graph[i].push(j);
                }
            }
        }
    }
    
    function dfs(bomb, visited) {
        visited[bomb] = true;
        let count = 1;
        
        for (const next of graph[bomb]) {
            if (!visited[next]) {
                count += dfs(next, visited);
            }
        }
        
        return count;
    }
    
    let maxBombs = 0;
    
    // 对每个炸弹进行DFS
    for (let i = 0; i < n; i++) {
        const visited = new Array(n).fill(false);
        const count = dfs(i, visited);
        maxBombs = Math.max(maxBombs, count);
    }
    
    return maxBombs;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
建图O(n²)O(n²)
n次DFSO(n²)O(n)
总计O(n²)O(n²)

其中 n 是炸弹的数量。建图需要检查所有炸弹对，每次DFS最多访问所有炸弹，空间主要用于存储邻接表和递归栈。

相关题目