假设我们有一个名为 points 的数组,其中一些点的形式为 (x, y)。现在连接两个点 (xi, yi) 和 (xj, yj) 的成本是它们之间的曼哈顿距离,公式为 |xi - xj| + |yi - yj|。我们必须找到使所有点连接的最低成本。
因此,如果输入类似于 points = [(0,0),(3,3),(2,10),(6,3),(8,0)],那么输出将为 22,因为
所以这里的总距离是 (6+5+3+8) = 22。
让我们看看以下实现以更好地理解 -
import heapq def solve(points): points_set = set(range(len(points))) heap = [(0, 0)] visited_node = set() total_distance = 0 while heap and len(visited_node) < len(points): distance, current_index = heapq.heappop(heap) if current_index not in visited_node: visited_node.add(current_index) points_set.discard(current_index) total_distance += distance x0, y0 = points[current_index] for next_index in points_set: x1, y1 = points[next_index] heapq.heappush(heap, (abs(x0 - x1) + abs(y0 - y1), next_index)) return total_distance points = [(0,0),(3,3),(2,10),(6,3),(8,0)] print(solve(points))
[(0,0),(3,3),(2,10),(6,3),(8,0)]输出结果
22