算法图算法

通过建图将问题转化为图上的搜索问题

字数统计: 911字   |   阅读时长: 3分
,

摘要: 难点在于正确建图

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个通过建图将问题转化为图上的搜索问题，难点在于正确建图。

题目

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

提示：

1
2
3
1 <= bombs.length <= 100
bombs[i].length == 3
1 <= xi, yi, ri <= 1e5

示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：

  • 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
  • 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
  • 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
    所以总共有 5 个炸弹被引爆。

题解

算法: 建图

将每个圆视为一个节点。对于两个节点 $i, j$，如果 $j$ 在 $i$ 的爆炸范围内，即引爆 $i$ 会进一步引爆 $j$，则链接有向边 $i \rightarrow j$；类似地，如果 $i$ 在 $j$ 的爆炸范围，则链接有向边 $j \rightarrow i$。

然后枚举图中的每个节点，将其作为起点在图中 DFS，可以搜索到的节点个数就是一个候选答案。

关于这个图有两个需要注意的地方，一个是该图是一个有向图，引爆 $i$ 可以进一步引爆 $j$ 不代表引爆 $j$ 可以进一步引爆 $i$，因此用并查集是不行的。另一个是图的边数最坏情况是 $O(N^{2})$，因此一次 DFS 的最坏时间复杂度为 $O(N^{2})$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        def dfs(u: int) -> int:
            cnt = 1
            for v in g[u]:
                if visited[v] == 1:
                    continue
                visited[v] = 1
                cnt += dfs(v)
            return cnt

        n = len(bombs)
        g = [[] for _ in range(n)]
        for i in range(n):
            xi, yi, ri = bombs[i]
            for j in range(i + 1, n):
                xj, yj, rj = bombs[j]
                dist = pow(xi - xj, 2) + pow(yi - yj, 2)
                if pow(ri, 2) >= dist:
                    g[i].append(j)
                if pow(rj, 2) >= dist:
                    g[j].append(i)
        visited = [0] * n
        ans = 0
        for s in range(n):
            if visited[s] == 1:
                continue
            visited[s] = 1
            ans = max(ans, dfs(s))
        return ans
Share