A chain reaction
Build a one-way graph from distances, then search from every starting point to find the biggest chain. About 14 minutes.
The graph is hidden in a rule
Each bomb has a position and a blast radius. When a bomb explodes, every bomb inside its radius explodes too. Which single bomb should you set off first to destroy the most bombs?
The graph isn't given, but it is easy to build. Bomb A has a one-way road to bomb B if B is inside A's blast. The roads are one-way because a large bomb may reach a small one without the small one reaching back. Then, for each starting bomb, count how many are reachable with a plain search.
- exploded
- 1
Start with bomb A. Its blast reaches B.
Bomb A's blast reaches bomb B. Does that mean B's blast reaches A?
- ANot necessarily, because the radii can differ
- BYes, distance works both ways
- CYes, and so they form one group
Show the answer
Not necessarily, because the radii can differ. Distance is the same both ways, but each bomb has its own radius.
Biggest chain reaction
bombs[i] = [x, y, r] describes a bomb at position (x, y) with blast radius r. When a bomb explodes, every other bomb whose position is within distance r of it (distance at most r) also explodes, and so on in a chain. Return the largest number of bombs that explode if you set off the best single bomb.
bombs = [[2, 1, 3], [6, 1, 4]] → 2
1 ≤ bombs ≤ 100 · 0 ≤ x, y ≤ 100,000 · 1 ≤ r ≤ 100,000