C++で各デカルト座標を接続するための最小コストを見つけるプログラム

2Dデカルト座標点（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]]、

（0、0）から（0、2）、（0、-2）、（2、0）、（-2、0）、コストは2、合計は8であるため、出力は14になります。 （2、3）は（0、2）に最も近く、コストは| 2 +1|です。 =3であり、（2、-3）の場合、（0、-2）に最も近く、コストも3です。したがって、合計コストは8 + 6=14です。

これを解決するには、次の手順に従います-

• MAX：=inf
• 関数interval（）を定義します。これには、i、j、およびポイント配列pが必要です。
• return |（p [i、x] --p [j、x]）+ | p [i、y] --p [j、y] ||
• メインの方法から、次の手順を実行します-
• n：=pのサイズ
• n <2の場合、0を返します
• 距離と呼ばれる配列をn個のスロットで定義し、MAXで埋めます
• 訪問したサイズnの配列を定義します
• 距離[0]：=0
• iを初期化する場合：=0、i
• min_d：=MAX
• node：=0
• jを初期化する場合：=0、j
• visited [j]がfalseで、distance [j]
• min_d：=distance [j]
• ノード：=j

例

理解を深めるために、次の実装を見てみましょう-

#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}}

出力

14