Posted on 2023-06-02 22:58
Uriel 阅读(24)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
有一堆二维圆形，给出每个圆形的中心坐标和半径，如果一个圆形A的覆盖范围包括了另一个圆B的圆心，则选了A就可以cover B，问点击其中某一个最多可以cover几个圆
DFS，注意若A能cover B，B不一定能cover A，所以每次要reset vis数组
1 #2101
2 #Runtime: 4068 ms (Beats 9.30%)
3 #Memory: 13.8 MB (Beats 58.14%)
4
5 class Solution(object):
6 def maximumDetonation(self, bombs):
7 """
8 :type bombs: List[List[int]]
9 :rtype: int
10 """
11
12 def In_Range(x, y):
13 if sqrt((bombs[x][1] - bombs[y][1])**2 + (bombs[x][0] - bombs[y][0])**2) <= bombs[x][2]:
14 return True
15 return False
16
17 def DFS(x):
18 for i in range(len(bombs)):
19 if not vis[i] and In_Range(x, i):
20 self.cnt += 1
21 vis[i] = 1
22 DFS(i)
23
24 ans = 0
25 for i in range(len(bombs)):
26 vis = [0] * len(bombs)
27 vis[i] = 1
28 self.cnt = 1
29 DFS(i)
30 ans = max(ans, self.cnt)
31 return ans