MediumRating 1880
2101. Detonate the Maximum Bombs
arraymathdepth-first-searchbreadth-first-searchgraphgeometry
解題說明
Detonate the Maximum Bombs
題目描述：
給定 n 個炸彈，每個以 [x, y, r] 表示（圓心座標和爆炸半徑）。引爆一個炸彈後，其爆炸範圍內的其他炸彈會連鎖引爆（被引爆的炸彈也會觸發自己範圍內的其他炸彈）。注意引爆關係是有向的：A 引爆 B 不代表 B 能引爆 A。求引爆一個炸彈能產生的最大連鎖引爆數量。
解題思路：
- 建圖：對每對炸彈
(i, j)，若炸彈i的爆炸範圍覆蓋炸彈j的圓心（即距離 <= r_i），則建一條有向邊i -> j。距離計算用平方避免浮點誤差。 - DFS/BFS 搜尋：對每個炸彈作為起點，用 DFS 或 BFS 計算能到達的節點數。
- 取所有起點中的最大值。
C++ 解法
複雜度分析
時間複雜度：O(n^3) — 建圖 O(n^2)，對每個起點 BFS 為 O(n + E)，共 n 次，最壞情況 E = O(n^2)。
空間複雜度：O(n^2) — 鄰接表儲存有向邊。
虛擬碼
1. Build directed graph:
For each pair (i, j):
If distance(bomb_i, bomb_j) <= radius_i:
Add edge i -> j
2. For each bomb i as starting point:
a. Run BFS/DFS from i
b. Count reachable nodes
3. Return maximum count其他解法
Floyd-Warshall O(n^3)：建立可達性矩陣，用傳遞閉包計算每個節點可達的節點數。時間複雜度相同但常數較大。
SCC 縮點 + 拓撲排序：先用 Tarjan 或 Kosaraju 找強連通分量，縮點後在 DAG 上計算最大可達節點數。時間複雜度 O(n^2)，但實作複雜度高，對 n <= 100 的限制不必要。
延伸思考
- 為什麼炸彈引爆關係是有向的？舉一個 A 能引爆 B 但 B 不能引爆 A 的例子。
- 如果可以同時引爆最多 k 個初始炸彈，如何最大化連鎖引爆數？
- 距離比較時為何使用平方而非開根號？這在哪些情況下重要？