C++程序:查找连接每个笛卡尔坐标的最小成本


假设我们有一组二维笛卡尔坐标点 (x, y)。我们可以连接 (x0, y0) 和 (x1, y1),其成本为 |x0 - x1| + |y0 - y1|。如果允许连接任意数量的点,则必须找到使每个点都通过路径连接所需的最小成本。

因此,如果输入类似于 points = [[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2, -3]],

则输出将为 14,因为从 (0, 0) 到 (0, 2)、(0, -2)、(2, 0)、(-2, 0) 的成本分别为 2,总计为 8,而 (2, 3) 最接近 (0, 2),成本为 |2+1| = 3,对于 (2, -3) 它最接近 (0, -2),成本也为 3。因此总成本为 8 + 6 = 14。

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

  • MAX := 无穷大
  • 定义一个函数 interval(),它将接收 i、j 和点数组 p,
  • 返回 |(p[i, x] - p[j, x]) + |p[i, y] - p[j, y]||
  • 从主方法中执行以下操作:
  • n := p 的大小
  • 如果 n < 2,则:返回 0
  • 定义一个名为 distance 的数组,包含 n 个槽,并填充为 MAX
  • 定义一个大小为 n 的名为 visited 的数组
  • distance[0] := 0
  • 对于初始化 i := 0,当 i < n 时,更新(i 增加 1),执行:
    • min_d := MAX
    • node := 0
    • 对于初始化 j := 0,当 j < n 时,更新(j 增加 1),执行:
      • 如果 visited[j] 为假且 distance[j] < min_d,则:
        • min_d := distance[j]
        • node := j
    • visited[node] := true
    • cost := cost + distance[node]
    • 对于初始化 j := 0,当 j < n 时,更新(j 增加 1),执行:
      • 如果 visited[j] 为假,则:
        • d := interval(node, j, p)
        • distance[j] := distance[j] 和 d 的最小值
  • 返回 cost

示例

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

Open Compiler
#include <iostream> #include <vector> #define MAX 99999 using namespace std; int interval(int i, int j, vector<vector<int>>& p) { return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]); } int solve(vector<vector<int>>& p) { int n = p.size(), cost = 0; if (n < 2) return 0; vector<int> distance(n, MAX); vector<bool> visited(n); distance[0] = 0; for (int i = 0; i < n; i++) { int min_d = MAX, node = 0; for (int j = 0; j < n; j++) { if (!visited[j] && distance[j] < min_d) { min_d = distance[j]; node = j; } } visited[node] = true; cost += distance[node]; for (int j = 0; j < n; j++) { if (!visited[j]) { int d = interval(node, j, p); distance[j] = min(distance[j], d); } } } return cost; } int main(){ vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}; cout << solve(points); }

输入

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

14

更新于:2021年10月16日

197 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告