Show problems as
Classic problem #2101MediumArrayMathDepth-First SearchBreadth-First SearchGraph TheoryGeometry

Detonate the Maximum Bombs

Real-world version: Largest Chain of Quarry Charges
Tracked in this browser only
Read Detonate the Maximum Bombs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A quarry crew has laid shaped charges across a flat working floor. Each entry of bombs describes one charge with three whole numbers: bombs[i][0] and bombs[i][1] are the coordinates of the point where charge i is buried, and bombs[i][2] is how far its shock wave carries.

Firing a charge also fires every charge buried at a straight-line distance no greater than that reach, and each charge fired that way then sets off whatever its own shock wave covers, and so on until nothing new goes off. A burial point sitting exactly at the limit of the reach does go off. Reaches differ from charge to charge, so one charge covering another does not mean the favour is returned.

The crew fires exactly one charge by hand. Return the largest number of charges that can end up fired, counting the hand-fired one.

Examples

Example 1

Input
bombs = [[1, 10, 11], [11, 10, 1], [21, 10, 11]]
Output
2

Firing charge 0 by hand covers charge 1, whose burial point is 10 away and inside its range of 11. Charge 1 has a range of only 1 and covers nothing, so two charges fire in total.

Example 2

Input
bombs = [[1, 1, 5], [1, 5, 5], [1, 9, 1]]
Output
3

Firing charge 0 covers charge 1, which lies 4 away and within its range of 5. Charge 1 in turn covers charge 2, which is another 4 away and within its own range of 5. All three fire.

Example 3

Input
bombs = [[1, 1, 5], [4, 5, 5]]
Output
2

The two burial points are 3 apart across and 4 apart up, so exactly 5 apart, and each charge has a range of 5. A point exactly on the rim counts, so firing either one fires both.

Constraints

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= x_i, y_i, r_i <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_detonation(bombs: list[list[int]]) -> int:
Java
public int maximumDetonation(int[][] bombs)

More on the same topics