LeetCode 2101: Detonate the Maximum Bombs (Directed Reachability + DFS)
LeetCode 2101GraphDFSToday we solve LeetCode 2101 - Detonate the Maximum Bombs.
Source: https://leetcode.com/problems/detonate-the-maximum-bombs/
English
Problem Summary
Each bomb is a node (x, y, r). If bomb i can reach bomb j (distance ≤ r_i), we add a directed edge i -> j. Starting from one bomb, all reachable nodes will explode. We need the maximum reachable count over all start nodes.
Key Insight
This is a directed reachability problem. Build the graph with squared distance comparison (avoid floating point), then run DFS/BFS from every node and keep the maximum visited size.
Algorithm
- Build adjacency list: for each pair i, j, add edge i -> j if (x_i-x_j)^2 + (y_i-y_j)^2 <= r_i^2.
- For each start node, run DFS and count visited nodes.
- Return the maximum count.
Complexity Analysis
Time: O(n^3) in worst case (graph build O(n^2) + DFS from each node O(n^2)).
Space: O(n^2) for adjacency list in dense case.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int maximumDetonation(int[][] bombs) {
int n = bombs.length;
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
long r2 = ri * ri;
for (int j = 0; j < n; j++) {
if (i == j) continue;
long dx = xi - bombs[j][0];
long dy = yi - bombs[j][1];
if (dx * dx + dy * dy <= r2) {
g.get(i).add(j);
}
}
}
int ans = 1;
for (int s = 0; s < n; s++) {
boolean[] vis = new boolean[n];
ans = Math.max(ans, dfsCount(s, g, vis));
}
return ans;
}
private int dfsCount(int u, List<List<Integer>> g, boolean[] vis) {
vis[u] = true;
int cnt = 1;
for (int v : g.get(u)) {
if (!vis[v]) cnt += dfsCount(v, g, vis);
}
return cnt;
}
}func maximumDetonation(bombs [][]int) int {
n := len(bombs)
g := make([][]int, n)
for i := 0; i < n; i++ {
xi, yi, ri := int64(bombs[i][0]), int64(bombs[i][1]), int64(bombs[i][2])
r2 := ri * ri
for j := 0; j < n; j++ {
if i == j {
continue
}
dx := xi - int64(bombs[j][0])
dy := yi - int64(bombs[j][1])
if dx*dx+dy*dy <= r2 {
g[i] = append(g[i], j)
}
}
}
var dfs func(int, []bool) int
dfs = func(u int, vis []bool) int {
vis[u] = true
cnt := 1
for _, v := range g[u] {
if !vis[v] {
cnt += dfs(v, vis)
}
}
return cnt
}
ans := 1
for s := 0; s < n; s++ {
vis := make([]bool, n)
c := dfs(s, vis)
if c > ans {
ans = c
}
}
return ans
}class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = (int)bombs.size();
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
long long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
long long r2 = ri * ri;
for (int j = 0; j < n; j++) {
if (i == j) continue;
long long dx = xi - bombs[j][0];
long long dy = yi - bombs[j][1];
if (dx * dx + dy * dy <= r2) {
g[i].push_back(j);
}
}
}
function<int(int, vector<int>&)> dfs = [&](int u, vector<int>& vis) {
vis[u] = 1;
int cnt = 1;
for (int v : g[u]) {
if (!vis[v]) cnt += dfs(v, vis);
}
return cnt;
};
int ans = 1;
for (int s = 0; s < n; s++) {
vector<int> vis(n, 0);
ans = max(ans, dfs(s, vis));
}
return ans;
}
};from typing import List
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
g = [[] for _ in range(n)]
for i in range(n):
xi, yi, ri = bombs[i]
r2 = ri * ri
for j in range(n):
if i == j:
continue
xj, yj, _ = bombs[j]
dx = xi - xj
dy = yi - yj
if dx * dx + dy * dy <= r2:
g[i].append(j)
def dfs(u: int, vis: List[bool]) -> int:
vis[u] = True
cnt = 1
for v in g[u]:
if not vis[v]:
cnt += dfs(v, vis)
return cnt
ans = 1
for s in range(n):
vis = [False] * n
ans = max(ans, dfs(s, vis))
return ansvar maximumDetonation = function(bombs) {
const n = bombs.length;
const g = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
const [xi, yi, ri] = bombs[i].map(BigInt);
const r2 = ri * ri;
for (let j = 0; j < n; j++) {
if (i === j) continue;
const xj = BigInt(bombs[j][0]);
const yj = BigInt(bombs[j][1]);
const dx = xi - xj;
const dy = yi - yj;
if (dx * dx + dy * dy <= r2) {
g[i].push(j);
}
}
}
function dfs(u, vis) {
vis[u] = true;
let cnt = 1;
for (const v of g[u]) {
if (!vis[v]) cnt += dfs(v, vis);
}
return cnt;
}
let ans = 1;
for (let s = 0; s < n; s++) {
const vis = new Array(n).fill(false);
ans = Math.max(ans, dfs(s, vis));
}
return ans;
};中文
题目概述
每个炸弹是一个点 (x, y, r)。若炸弹 i 的爆炸半径能覆盖炸弹 j，则存在有向边 i -> j。从一个起点炸弹引爆后，会连锁引爆所有可达炸弹。要求最大可引爆数量。
核心思路
把问题转成有向图可达性。先用“平方距离 ≤ 半径平方”建图（避免浮点误差），再从每个节点做 DFS/BFS，统计可达节点个数并取最大值。
算法步骤
- 双层循环判断是否存在边 i -> j，构建邻接表。
- 以每个炸弹为起点，执行一次 DFS。
- 记录该次访问到的节点数，更新全局最大值。
复杂度分析
时间复杂度：最坏 O(n^3)（建图 O(n^2)，每个起点 DFS 总计 O(n^2)）。
空间复杂度：最坏 O(n^2)（稠密图邻接表）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int maximumDetonation(int[][] bombs) {
int n = bombs.length;
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
long r2 = ri * ri;
for (int j = 0; j < n; j++) {
if (i == j) continue;
long dx = xi - bombs[j][0];
long dy = yi - bombs[j][1];
if (dx * dx + dy * dy <= r2) {
g.get(i).add(j);
}
}
}
int ans = 1;
for (int s = 0; s < n; s++) {
boolean[] vis = new boolean[n];
ans = Math.max(ans, dfsCount(s, g, vis));
}
return ans;
}
private int dfsCount(int u, List<List<Integer>> g, boolean[] vis) {
vis[u] = true;
int cnt = 1;
for (int v : g.get(u)) {
if (!vis[v]) cnt += dfsCount(v, g, vis);
}
return cnt;
}
}func maximumDetonation(bombs [][]int) int {
n := len(bombs)
g := make([][]int, n)
for i := 0; i < n; i++ {
xi, yi, ri := int64(bombs[i][0]), int64(bombs[i][1]), int64(bombs[i][2])
r2 := ri * ri
for j := 0; j < n; j++ {
if i == j {
continue
}
dx := xi - int64(bombs[j][0])
dy := yi - int64(bombs[j][1])
if dx*dx+dy*dy <= r2 {
g[i] = append(g[i], j)
}
}
}
var dfs func(int, []bool) int
dfs = func(u int, vis []bool) int {
vis[u] = true
cnt := 1
for _, v := range g[u] {
if !vis[v] {
cnt += dfs(v, vis)
}
}
return cnt
}
ans := 1
for s := 0; s < n; s++ {
vis := make([]bool, n)
c := dfs(s, vis)
if c > ans {
ans = c
}
}
return ans
}class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = (int)bombs.size();
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
long long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
long long r2 = ri * ri;
for (int j = 0; j < n; j++) {
if (i == j) continue;
long long dx = xi - bombs[j][0];
long long dy = yi - bombs[j][1];
if (dx * dx + dy * dy <= r2) {
g[i].push_back(j);
}
}
}
function<int(int, vector<int>&)> dfs = [&](int u, vector<int>& vis) {
vis[u] = 1;
int cnt = 1;
for (int v : g[u]) {
if (!vis[v]) cnt += dfs(v, vis);
}
return cnt;
};
int ans = 1;
for (int s = 0; s < n; s++) {
vector<int> vis(n, 0);
ans = max(ans, dfs(s, vis));
}
return ans;
}
};from typing import List
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
g = [[] for _ in range(n)]
for i in range(n):
xi, yi, ri = bombs[i]
r2 = ri * ri
for j in range(n):
if i == j:
continue
xj, yj, _ = bombs[j]
dx = xi - xj
dy = yi - yj
if dx * dx + dy * dy <= r2:
g[i].append(j)
def dfs(u: int, vis: List[bool]) -> int:
vis[u] = True
cnt = 1
for v in g[u]:
if not vis[v]:
cnt += dfs(v, vis)
return cnt
ans = 1
for s in range(n):
vis = [False] * n
ans = max(ans, dfs(s, vis))
return ansvar maximumDetonation = function(bombs) {
const n = bombs.length;
const g = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
const [xi, yi, ri] = bombs[i].map(BigInt);
const r2 = ri * ri;
for (let j = 0; j < n; j++) {
if (i === j) continue;
const xj = BigInt(bombs[j][0]);
const yj = BigInt(bombs[j][1]);
const dx = xi - xj;
const dy = yi - yj;
if (dx * dx + dy * dy <= r2) {
g[i].push(j);
}
}
}
function dfs(u, vis) {
vis[u] = true;
let cnt = 1;
for (const v of g[u]) {
if (!vis[v]) cnt += dfs(v, vis);
}
return cnt;
}
let ans = 1;
for (let s = 0; s < n; s++) {
const vis = new Array(n).fill(false);
ans = Math.max(ans, dfs(s, vis));
}
return ans;
};
Comments