Posted on 2023-06-02 22:58
Uriel 閱讀(31)
評論(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