सभी दिए गए निर्देशांकों की यात्रा की लागत का पता लगाने के लिए C++ प्रोग्राम

मान लीजिए, हमें n त्रि-आयामी निर्देशांक दिए गए हैं। निर्देशांक (a, b, c) से (x, y, z) तक यात्रा करने की लागत ∣ x - a∣ + ∣ y - b∣ + max(0, z - c) है। हम पहले निर्देशांक से शुरू करते हैं, फिर कम से कम एक बार सभी निर्देशांक पर जाते हैं, और फिर पहले निर्देशांक पर लौटते हैं। हमें इस पूरी यात्रा की कुल लागत का पता लगाना है। निर्देशांक हमें सरणी 'कोर्ड्स' में दिए गए हैं।

इसलिए, यदि इनपुट n =3, कोर्ड्स ={{1, 1, 0}, {1, 3, 4}, {3, 2, 2}} जैसा है, तो आउटपुट 12 होगा।

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

Define one 2D array tpa.
tpa[1, 0] := 0
   for initialize i := 1, when i < 2n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if i mod 2 is same as 0, then:
            Ignore following part, skip to the next iteration
               for initialize t := 0, when t < n, update (increase t by 1), do:
                  x := first value of coords[t]
                  y := second value of coords[t]
                  z := third value of coords[t]
                  p := first value of coords[j]
                  q := second value of coords[j]
                r := third value of coords[j]
tpa[i OR (1 bitwise left shift t)][t] := minimum of (tpa[i|(1 bitwise left shift t)][t], tpa[i][j] + |x - p| + |y - q| + maximum of (0, z - r))
res := infinity
for initialize i := 0, when i < n, update (increase i by 1), do:
x := first value of coords[0]
y := second value of coords[0]
z := third value of coords[0]
p := first value of coords[i]
q := second value of coords[i]
r := third value of coords[i]
res := minimum of (res and tpa[2n - 1, i] + |x - p| + |y - q| + maximum of (0 and z - r))
return res

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int solve(int n, vector<tuple<int,int,int>> coords){
   vector<vector<int>> tpa(pow(2, n), vector<int>(n, INF));
   tpa[1][0] = 0;
   for(int i = 1; i < pow(2,n); i++) {
      for(int j = 0; j < n; j++){
         if(i % 2 == 0)
            continue;
         for(int t = 0; t < n; t++) {
            int x, y, z, p, q, r;
            tie(x, y, z) = coords[t];
            tie(p, q, r) = coords[j];
            tpa[i | (1 << t)][t] = min(tpa[i|(1 << t)][t], tpa[i][j] + abs(x - p) + abs(y - q) + max(0, z - r));
         }
      }
   }
   int res = INF;
   for(int i = 0; i < n; i++) {
      int x, y, z, p, q, r;
      tie(x, y, z) = coords[0];
      tie(p, q, r) = coords[i];
      res = min(res, tpa[pow(2, n) - 1][i] + abs(x - p) + abs(y - q) + max(0, z - r));
   }
   return res;
}
int main() {
   int n = 3;
   vector<tuple<int,int,int>> coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}};
   cout<< solve(n, coords);
   return 0;
}

इनपुट

3, {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}

आउटपुट

12