C++ এ প্রতিটি কার্টেসিয়ান স্থানাঙ্ক সংযোগ করার জন্য সর্বনিম্ন খরচ খুঁজে বের করার জন্য প্রোগ্রাম

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

সুতরাং, যদি ইনপুট পয়েন্টের মত হয় =[[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2] , -3]],

তাহলে আউটপুট হবে 14 কারণ, (0, 0) থেকে (0, 2), (0, -2), (2, 0), (-2, 0), খরচ 2, মোট 8, এবং (2, 3) (0, 2) থেকে সবচেয়ে কাছের, খরচ হল |2+1| =3 এবং (2, -3) এর জন্য এটি (0, -2) এর নিকটতম, খরচও 3। তাই মোট খরচ হল 8 + 6 =14।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• MAX :=inf
• একটি ফাংশন ব্যবধান () সংজ্ঞায়িত করুন, এটি i, j, এবং পয়েন্ট অ্যারে p গ্রহণ করবে,
• রিটার্ন |(p[i, x] - p[j, x]) + |p[i, y] - p[j, y]||
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• n :=p এর আকার
• যদি n <2 হয়, তাহলে:0 ফেরত দিন
• n স্লট সহ দূরত্ব নামক একটি অ্যারে সংজ্ঞায়িত করুন এবং MAX দিয়ে পূরণ করুন
• n আকারের পরিদর্শন করা একটি অ্যারে সংজ্ঞায়িত করুন
• দূরত্ব[0] :=0
• আরম্ভ করার জন্য i :=0, যখন i করুন
• min_d :=MAX
• নোড :=0
• j শুরু করার জন্য :=0, যখন j করুন
• যদি পরিদর্শন করা হয় [j] মিথ্যা এবং দূরত্ব [j]
• min_d :=দূরত্ব[j]
• নোড :=j

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include #include #define MAX 99999 namespace ব্যবহার করে std;int interval(int i, int j, vector>&p) { রিটার্ন abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);}int solve(vector>&p) { int n =p.size (), খরচ =0; যদি (n <2) 0 ফেরত দেয়; ভেক্টর দূরত্ব(n, MAX); ভেক্টর পরিদর্শন করা হয়েছে(n); দূরত্ব [0] =0; জন্য (int i =0; i > পয়েন্ট ={{0, 0},{0, 2},{0, -2},{2, 0},{-2 , 0}, {2, 3}, {2, -3}};cout < 
ইনপুট
 
{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}} 
আউটপুট
 
14