🔗 🟡 2101. Detonate the Maximum Bombs 1880

tags: `Biweekly Contest 67` `DFS` `BFS` `陣列(Array)` `圖(Graph)` `幾何(Geometry)` `數學(Math)` `BitSet` `Floyd-Warshall`

題意

一個炸彈的爆炸範圍定義為以炸彈為圓心的一個圓。

給定一個二維整數陣列 $bombs$ ，其中 $bombs[i] = [x_i, y_i, r_i]$ 表示第 $i$ 個炸彈的 x 和 y 座標， $r_i$ 表示爆炸範圍的半徑。

你可以選擇引爆一枚炸彈。當這個炸彈被引爆時，它會引爆所有在其爆炸範圍內的炸彈，這些被引爆的炸彈會進一步引爆它們爆炸範圍內的其他炸彈。

返回在選擇一枚炸彈引爆後下，最多可以引爆的炸彈數量。

思路：DFS

首先考慮要如何定義炸彈之間的關係，如果炸彈 $i$ 的爆炸範圍包含炸彈 $j$ ，則炸彈 $i$ 可以引爆炸彈 $j$ 。因此可以使用有向圖(Directed Graph) 來表示炸彈之間的關係，並使用一個鄰接表(Adjacency List) 來存儲這個有向圖。

這裡需要注意，炸彈之間的關係是單向的，即炸彈 $i$ 可以引爆炸彈 $j$ ，但炸彈 $j$ 不一定可以引爆炸彈 $i$ 。故不能使用無向圖來表示炸彈之間的關係。

在得到了有向圖之後，就可以使用深度優先搜索(DFS) 的方式來計算從每個炸彈開始可以引爆的最大炸彈數量。定義一個遞迴函數 dfs 來進行深度優先搜索。這個函數會從一個炸彈開始，標記其為已訪問，然後遞迴地訪問所有在其爆炸範圍內的炸彈，並累計引爆的炸彈數量。在 DFS 過程中，使用一個陣列 $\text{vis}$ 來記錄已經探索過的炸彈，避免重複訪問。

最後，遍歷所有的炸彈，計算其可以引爆的炸彈數量，找到可以引爆的最大炸彈數量，作為最終的答案返回。

複雜度分析

時間複雜度： $\mathcal{O}(n^3)$ $O (n^{3})$ ，其中 $n$ $n$ 是炸彈的數量。
- 建立鄰接表的時間複雜度為 $\mathcal{O}(n^2)$ ，因為需要檢查每對炸彈之間的關係。
- 每次 DFS 的時間複雜度為 $\mathcal{O}(n^2)$ $O (n^{2})$ ，且總共需要執行 $n$ $n$ 次 DFS。
  - 最壞情況下，每個點之間都有邊相連，都可以引爆其他所有炸彈，因此在訪問到某一個點時，都需要檢查其他所有點，且每個點都會被訪問一次。
空間複雜度： $\mathcal{O}(n^2)$ $O (n^{2})$ 。
- 鄰接表的空間複雜度為 $\mathcal{O}(n^2)$ 。

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        g = [[] for _ in range(n)]
        for i, (x1, y1, r1) in enumerate(bombs):
            for j, (x2, y2, _) in enumerate(bombs):
                if i == j:
                    continue
                if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r1 ** 2:
                    g[i].append(j)

        def dfs(i: int) -> int:
            vis[i] = True
            res = 1
            for j in g[i]:
                if not vis[j]:
                    res += dfs(j)
            return res

        ans = 0
        for i in range(n):
            vis = [False] * n
            ans = max(ans, dfs(i))
        return ans

class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (pow(bombs[i][0] - bombs[j][0], 2) + pow(bombs[i][1] - bombs[j][1], 2) <= pow(bombs[i][2], 2)) {
                    g[i].push_back(j);
                }
            }
        }

        vector<bool> vis(n, false);
        function<int(int)> dfs = [&](int i) {
            vis[i] = true;
            int res = 1;
            for (int j : g[i]) {
                if (!vis[j]) res += dfs(j);
            }
            return res;
        };

        int ans = 0;
        for (int i = 0; i < n; i++) {
            vis.assign(n, false);
            ans = max(ans, dfs(i));
        }
        return ans;
    }
};