C++-এ ৩D কোঅর্ডিনেট ভ্রমণের মোট খরচ বের করুন

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int solve(int n, vector<tuple<int,int,int>> coords) {
    vector<vector<int>> tpa(1 << n, vector<int>(n, INF));
    tpa[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int j = 0; j < n; j++) {
            if (mask % 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];
                int cost = abs(x - p) + abs(y - q) + max(0, z - r);
                tpa[mask | (1 << t)][t] = min(tpa[mask | (1 << t)][t], tpa[mask][j] + cost);
            }
        }
    }
    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];
        int cost = abs(x - p) + abs(y - q) + max(0, z - r);
        res = min(res, tpa[(1 << n) - 1][i] + cost);
    }
    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;
}

আউটপুট

12

ব্যাখ্যা

• স্টেট: mask = ভিজিট করা নোডগুলো, last = বর্তমান নোড।
• ট্রানজিশন: mask থেকে নতুন নোড t যোগ।
• কমপ্লেক্সিটি: O(n^2 * 2^n) — ছোট n (≤15-20) এর জন্য কাজ করে।
• max(0, z-c) এর মানে: যাত্রা উপরের দিকে (z বাড়ানোর সময়) খরচ হয়, নিচের দিকে নয়।