C++-এ কার্টেসিয়ান কোঅর্ডিনেট পয়েন্টগুলোর মিনিমাম কানেকশন খরচ বের করার প্রোগ্রাম

ধরা যাক ২D কার্টেসিয়ান কোঅর্ডিনেট পয়েন্টের একটি লিস্ট দেওয়া আছে (x, y)। দুটি পয়েন্ট (x0, y0) এবং (x1, y1) কানেক্ট করার খরচ হলো |x0 - x1| + |y0 - y1| (ম্যানহ্যাটন দূরত্ব)। যেকোনো সংখ্যক পয়েন্ট কানেক্ট করা যেতে পারে। এমনভাবে কানেক্ট করতে হবে যাতে প্রতিটি পয়েন্ট পথ দ্বারা একে অপরের সাথে সংযুক্ত থাকে এবং মোট খরচ ন্যূনতম হয়।

উদাহরণস্বরূপ, points = [[0,0],[0,2],[0,-2],[2,0],[-2,0],[2,3],[2,-3]] হলে আউটপুট হবে ১৪।

(0,0) থেকে (0,2), (0,-2), (2,0), (-2,0) কানেক্ট করার খরচ ২+২+২+২=৮। (2,3) (0,2)-এর নিকটতম, খরচ |2|+|1|=৩। (2,-3) (0,-2)-এর নিকটতম, খরচ ৩। মোট = ৮+৩+৩ = ১৪।

সমাধানের ধাপসমূহ

এটি মিনিমাম স্প্যানিং ট্রি (MST) সমস্যা, প্রিমের অ্যালগরিদম ব্যবহার করুন
MAX := INF
interval(i, j, p) ফাংশন: |p[i][0]-p[j][0]| + |p[i][1]-p[j][1]| রিটার্ন করুন
প্রধান ফাংশনে:
- n := p-এর আকার, যদি n < 2 হয় তবে ০ রিটার্ন করুন
- distance অ্যারে (আকার n, INIT MAX), visited অ্যারে (আকার n)
- distance[0] := ০
- n বার লুপ চালান:
  - অনভিজিটেড নোড থেকে min_d এবং node বের করুন
  - visited[node] = true, cost += distance[node]
  - প্রতিটি অনভিজিটেড নোড j-এর জন্য distance[j] = min(distance[j], interval(node, j, p)) আপডেট করুন
- cost রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

#include <iostream> #include <vector> #define MAX 99999 using namespace std; int interval(int i, int j, vector<vector<int>>& p) {    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]); } int solve(vector<vector<int>>& p) {    int n = p.size(), cost = 0;    if (n < 2) return 0;    vector<int> distance(n, MAX);    vector<bool> visited(n);    distance[0] = 0;    for (int i = 0; i < n; i++) {       int min_d = MAX, node = 0;       for (int j = 0; j < n; j++) {          if (!visited[j] && distance[j] < min_d) {             min_d = distance[j];             node = j;          }       }       visited[node] = true;       cost += distance[node];       for (int j = 0; j < n; j++) {          if (!visited[j]) {             int d = interval(node, j, p);             distance[j] = min(distance[j], d);          }       }    }    return cost; } int main(){    vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}; cout << solve(points); }

ইনপুট

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}