मान लीजिए 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 होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक 2D सरणी tpa परिभाषित करें
tpa[1][0] := 0
i := 1 से 2^n-1 तक:
j := 0 से n-1 तक:
यदि i % 2 == 0, तो जारी रखें
t := 0 से n-1 तक:
x := coords[t] का पहला मान
y := coords[t] का दूसरा मान
z := coords[t] का तीसरा मान
p := coords[j] का पहला मान
q := coords[j] का दूसरा मान
r := coords[j] का तीसरा मान
tpa[i | (1 << t)][t] := min(tpa[i | (1 << t)][t], tpa[i][j] + |x-p| + |y-q| + max(0, z-r))
res := अनंत
i := 0 से n-1 तक:
x := coords[0] का पहला मान
y := coords[0] का दूसरा मान
z := coords[0] का तीसरा मान
p := coords[i] का पहला मान
q := coords[i] का दूसरा मान
r := coords[i] का तीसरा मान
res := min(res, tpa[2^n-1][i] + |x-p| + |y-q| + max(0, z-r))
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