0548MediumArrayMathDepth-First SearchBreadth-First SearchGraph TheoryGeometry

Largest Chain of Quarry Charges

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_detonation(bombs: list[list[int]]) -> int:

Java

public int maximumDetonation(int[][] bombs)

The intended approach

Time O(n^3) in the worst case: building the links costs O(n^2) and each of the n sweeps walks up to O(n^2) links.Space O(n^2) for the link lists.

Coverage is one-way, so record it as a directed link list: put a link from `i` to `j` when `j`'s burial point falls inside charge `i`'s range. Compare the squared separation against the squared range so the test stays in whole numbers and a point sitting exactly on the rim counts as covered. Then run a breadth-first sweep along the links from each charge in turn, counting how many charges the sweep reaches, and report the largest count. Every start has to be tried because the charge that ends up firing the most is not necessarily the one with the longest range.

Pythonentry point: maximum_detonation

def maximum_detonation(bombs):
    # Build a one-way link list with squared distances so no square roots and no
    # floating point are involved, then run a breadth-first sweep from each
    # charge in turn and keep the largest set reached.
    from collections import deque
    n = len(bombs)
    links = [[] for _ in range(n)]
    for i in range(n):
        xi, yi, ri = bombs[i]
        span = ri * ri
        for j in range(n):
            if i == j:
                continue
            dx = xi - bombs[j][0]
            dy = yi - bombs[j][1]
            if dx * dx + dy * dy <= span:
                links[i].append(j)
    best = 0
    for start in range(n):
        fired = [False] * n
        fired[start] = True
        count = 1
        queue = deque([start])
        while queue:
            cur = queue.popleft()
            for nxt in links[cur]:
                if not fired[nxt]:
                    fired[nxt] = True
                    count += 1
                    queue.append(nxt)
        if count > best:
            best = count
    return best

The obvious version

Fill an n by n table of direct coverage, then close it under composition: for every middle charge k, whenever i reaches k and k reaches j, mark that i reaches j. Repeating that for each k in turn leaves each row holding everything reachable from that charge, so the answer is the fullest row.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_detonation(bombs):
    n = len(bombs)
    reach = [[False] * n for _ in range(n)]
    for i in range(n):
        reach[i][i] = True
        for j in range(n):
            if i == j:
                continue
            dx = bombs[i][0] - bombs[j][0]
            dy = bombs[i][1] - bombs[j][1]
            if dx * dx + dy * dy <= bombs[i][2] * bombs[i][2]:
                reach[i][j] = True
    for k in range(n):
        for i in range(n):
            if reach[i][k]:
                for j in range(n):
                    if reach[k][j]:
                        reach[i][j] = True
    best = 0
    for i in range(n):
        count = 0
        for j in range(n):
            if reach[i][j]:
                count += 1
        if count > best:
            best = count
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in