সমস্ত প্রদত্ত স্থানাঙ্ক ভ্রমণের খরচ খুঁজে বের করতে C++ প্রোগ্রাম

ধরুন, আমাদের n ত্রিমাত্রিক স্থানাঙ্ক দেওয়া হয়েছে। স্থানাঙ্ক (a, b, c) থেকে (x, y, z) যাওয়ার খরচ হল ∣ x − a∣ + ∣ y − b∣ + সর্বোচ্চ(0, z − c)। আমরা প্রথম স্থানাঙ্ক থেকে শুরু করি, তারপর অন্তত একবার সমস্ত স্থানাঙ্ক পরিদর্শন করি এবং তারপর প্রথম স্থানাঙ্কে ফিরে যাই। আমাদের এই পুরো ট্রিপের মোট খরচ বের করতে হবে। স্থানাঙ্কগুলি আমাদের অ্যারে 'কোর্ডস'-এ দেওয়া হয়।

সুতরাং, যদি ইনপুট n =3, coords ={{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