在Python中将一组点分为k个不同组的程序

假设我们有一个点列表和一个数字k。这些点的形式为(x,y)，代表笛卡尔坐标。如果两个点p1和p2之间的欧式距离小于等于k，则可以将它们分组，我们必须找到不相交的组的总数。

因此，如果输入像点= [[2，2]，[3，3]，[4，4]，[11，11]，[12，12]]，k = 2，则输出将为2，因为它可以分为两组：[[2,2]，[3,3]，[4,4]）和（[11,11]，[12,12]）

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能dfs()。这需要我

• 如果我在里面，那么

• dfs(nb)

• 从主要方法，请执行以下操作-

• adj：=映射

• n：=点的大小

• 对于0到n范围内的j，执行

• 看过：=一套新的

• 回答：= 0

• 对于0到n范围内的i，执行

• 返回ans

• p1：=分[i]

• p2：=分[j]

• 如果p1和p2之间的欧几里得距离<k，则

• 在adj [i]的末尾插入j

• 在adj [j]的末尾插入i

• 对于0到j范围内的i，执行

• ans：= ans + 1

• dfs(i)

• 如果我没看到，那

• 返回

• 将我插入看到

• 对于adj [i]中的每个nb，执行

让我们看下面的实现以更好地理解-

示例

from collections import defaultdict
class Solution:
   def solve(self, points, k):
      adj = defaultdict(list)

      n = len(points)
      for j in range(n):
         for i in range(j):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2:
               adj[i].append(j)
               adj[j].append(i)

      seen = set()      def dfs(i):
         if i in seen:
            return
         seen.add(i)
         for nb in adj[i]:
            dfs(nb)

      ans = 0
      for i in range(n):
         if i not in seen:
            ans += 1
            dfs(i)
      return ans
ob = Solution()points = [
[2, 2],
[3, 3],
[4, 4],
[11, 11],
[12, 12]
]
k = 2
print(ob.solve(points, k))

输入值

[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2

输出结果

2