โปรแกรมหาต้นทุนขั้นต่ำในการเชื่อมต่อแต่ละพิกัดคาร์ทีเซียนใน C++

สมมติว่าเรามีรายการจุดพิกัดคาร์ทีเซียน 2 มิติ (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 :=ขนาดของพี
• ถ้า n <2 แล้ว:คืนค่า 0
• กำหนดอาร์เรย์ที่เรียกว่าระยะทางด้วย n ช่องและเติมด้วย MAX
• กำหนดอาร์เรย์ที่เข้าชมขนาด n
• ระยะทาง[0] :=0
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• min_d :=MAX
• โหนด :=0
• สำหรับการเริ่มต้น j :=0 เมื่อ j
• ถ้าไป[j] เป็นเท็จ และระยะทาง[j]
• min_d :=ระยะทาง[j]
• โหนด :=เจ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include #include #define MAX 99999 โดยใช้เนมสเปซ std;int ช่วง (int i, int j, vector>&p) { return abs (p [i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);}int แก้ปัญหา(vector>&p) { int n =p.size (), ราคา =0; ถ้า (n <2) คืนค่า 0; เวกเตอร์  ระยะทาง (n, MAX); vector เข้าชมแล้ว (n); ระยะทาง[0] =0; สำหรับ (int i =0; i > points ={{0, 0},{0, 2},{0, -2},{2, 0},{-2 , 0}, {2, 3}, {2, -3}};cout <<แก้ (คะแนน);}

อินพุต

ผลลัพธ์

14