2101.引爆最多的炸弹

链接：2101.引爆最多的炸弹
难度：Medium
标签：深度优先搜索、广度优先搜索、图、几何、数组、数学
简介：给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

题解 1 - python

• 编辑时间：2024-07-22
• 执行用时：510ms
• 内存消耗：17.08MB
• 编程语言：python
• 解法介绍：遍历存储所有爆炸链接后dfs。

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        nexts = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j:
                    if (bombs[i][0] - bombs[j][0]) ** 2 + (bombs[i][1] - bombs[j][1]) ** 2 <= bombs[i][2] ** 2:
                        nexts[i].append(j)
        def dfs(cur: int, used: List[bool]) -> int:
            used[cur] = True
            return sum(
                dfs(next, used)
                for next in nexts[cur]
                if not used[next]
            ) + 1
        return max(dfs(i, [False] * n) for i in range(n))