โปรแกรม C++ หาค่าเดินทางตามพิกัดที่ให้มาทั้งหมด

สมมติว่าเราได้รับ n พิกัดสามมิติ ค่าใช้จ่ายในการเดินทางจากพิกัด (a, b, c) ถึง (x, y, z) คือ ∣ x − a∣ + ∣ y − b∣ + max(0, z − c) เราเริ่มต้นจากพิกัดแรก จากนั้นไปที่พิกัดทั้งหมดอย่างน้อยหนึ่งครั้ง จากนั้นกลับไปที่พิกัดแรก เราต้องหาค่าใช้จ่ายทั้งหมดของทริปนี้ให้ได้ พิกัดนั้นมอบให้เราใน 'coords' ของอาร์เรย์

ดังนั้น หากอินพุตเป็น 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