C++ में प्रत्येक कार्तीय निर्देशांक को जोड़ने के लिए न्यूनतम लागत ज्ञात करने का कार्यक्रम

मान लीजिए कि हमारे पास 2D कार्टेशियन निर्देशांक बिंदुओं (x, y) की एक सूची है। हम (x0, y0) और (x1, y1) को जोड़ सकते हैं, जिसकी लागत |x0 - x1| + |y0 - y1|। यदि हमें किसी भी संख्या में बिंदुओं को जोड़ने की अनुमति दी जाती है, तो हमें आवश्यक न्यूनतम लागत का पता लगाना होगा जैसे कि प्रत्येक बिंदु एक पथ से जुड़ा हो।

इसलिए, यदि इनपुट अंक की तरह है =[[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 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अधिकतम:=जानकारी
• फ़ंक्शन अंतराल () को परिभाषित करें, इसमें i, j, और पॉइंट एरे p,
लगेगा
• रिटर्न |(p[i, x] - p[j, x]) + |p[i, y] - p[j, y]||
• मुख्य विधि से, निम्न कार्य करें -
• n :=p का आकार
• अगर n <2, तो:वापसी 0
• एन स्लॉट के साथ दूरी नामक एक सरणी को परिभाषित करें और MAX से भरें
• एक ऐसी सरणी परिभाषित करें जो n आकार में देखी गई हो
• दूरी[0] :=0
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• min_d :=MAX
• नोड:=0
• इनिशियलाइज़ j :=0 के लिए, जब j करें
• यदि विज़िट किया गया है[j] गलत है और दूरी है[j]
• min_d:=दूरी[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