จุดนัดพบที่ดีที่สุดใน C++

สมมติว่ามีกลุ่มคนตั้งแต่สองคนขึ้นไปและพวกเขาต้องการพบปะและลดระยะทางการเดินทางทั้งหมด เรามีตาราง 2D ของค่า 0 หรือ 1 โดยที่แต่ละค่า 1 ทำเครื่องหมายบ้านของใครบางคนในกลุ่ม ระยะทางคำนวณโดยใช้สูตรของ Manhattan Distance ดังนั้น Distance(p1, p2) =|p2.x - p1.x| + |p2.y - p1.y|.

ดังนั้นหากอินพุตเป็นแบบ

ผลลัพธ์จะเป็น 6 จากเมทริกซ์ เราเข้าใจได้ว่ามีคนสามคนอาศัยอยู่ที่ (0,0) (0,4) และ (2,2):จุด (0,2 ) เป็นจุดนัดพบในอุดมคติ เนื่องจากระยะทางการเดินทางรวม 2+2+2=6 เป็นอย่างต่ำ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน get() ซึ่งจะใช้อาร์เรย์ v

• จัดเรียงอาร์เรย์ v

• ผม :=0

• j :=ขนาดของวี

• ยกเลิก :=0

• ในขณะที่ฉัน

  • ret :=ret + v[j] - v[i]

  • (เพิ่ม i ขึ้น 1)

  • (ลด j โดย 1)

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดแถวอาร์เรย์

• กำหนดคอลัมน์อาร์เรย์

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของกริด อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า grid[i, j] ไม่ใช่ศูนย์ ดังนั้น −

      • ใส่ i ที่ท้ายแถว

      • ใส่ j ต่อท้าย col

• ส่งคืน get(row) + get(col)

ตัวอย่าง

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

#include ใช้ namespace std;class Solution {public:int minTotalDistance(vector>&grid) { vector  row; เวกเตอร์ col; สำหรับ (int i =0; i  v){ sort(v.begin(), v.end()); int ผม =0; int j =v.size() - 1; int ret =0; ในขณะที่ (i > v ={{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}; ศาล <<(ob.minTotalDistance(v));}

อินพุต

เอาท์พุต

6