ในโจทย์นี้ เราได้รับอาร์เรย์ไบนารี 2 มิติ นั่นคือ มีค่าเป็น 0 หรือ 1 โดยที่ 1 หมายถึงบ้านของคนในกลุ่ม และคนในกลุ่มต้องการพบปะกัน ดังนั้นพวกเขาต้องลดระยะทางรวมที่เดินทางเพื่อพบกันที่จุดร่วม จุดพบปะที่ถูกต้องสามารถอยู่ที่ไหนก็ได้ แต่ไม่ใช่ที่บ้านของใคร
เพื่อหาระยะทางขั้นต่ำ สูตรถูกสร้างขึ้น ชื่อว่า Manhattan distance โดยระยะทาง −
(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
มาดูตัวอย่าง เพื่อทำให้แนวคิดชัดเจน
ตัวอย่าง
Input: {10001} {00000} {00100} Output: 6คำอธิบาย − จุดพบปะที่ดีที่สุดคือ (0,2) ซึ่งทำให้ระยะทางที่เดินทางเท่ากับ 6 (2+2+2)
ตอนนี้ มาสร้างวิธีแก้ปัญหา ที่นี่เราต้องหาจุดกลางจากจุดทั้งหมดที่ทำเครื่องหมาย 1 ในอาร์เรย์ เราจะทำโดยการหาจุดกึ่งกลางแนวนอนและแนวตั้งแยกกัน และคำนวณระยะทางจากจุดนั้นไปยังจุดที่ทำเครื่องหมาย 1 ทั้งหมด
อัลกอริทึม
ขั้นตอนที่ 1 : สร้างโครงสร้างสองชุดเก็บตำแหน่งแนวนอนและแนวตั้งของจุดที่ทำเครื่องหมาย 1 ขั้นตอนที่ 2 : ในทั้งสองโครงสร้าง หาตำแหน่งกึ่งกลาง และถือว่า (midx, midy) เป็นจุดพบปะ ขั้นตอนที่ 3 : คำนวณระยะทางของแต่ละจุดไปยังจุดกึ่งกลาง ขั้นตอนที่ 4 : คืนค่าผลรวมของระยะทางทั้งหมด
ตัวอย่าง
มาสร้างอัลกอริทึมตามข้างต้น −
#include <bits/stdc++.h> using namespace std; #define ROW 3 #define COL 5 int minMeetingDistance(int grid[][COL]) { if (ROW == 0 || COL == 0) return 0; vector<int> vertical; vector<int> horizontal; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (grid[i][j] == 1) { vertical.push_back(i); horizontal.push_back(j); } } } sort(vertical.begin(),vertical.end()); sort(horizontal.begin(),horizontal.end()); int size = vertical.size()/2; int midx = vertical[size]; int midy = horizontal[size]; int distance = 0; for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) if (grid[i][j] == 1) distance += abs(midx - i) + abs(midy - j); return distance; } int main() { int distance[ROW][COL] = {{1, 0, 1, 0, 1}, {0, 0, 0, 1, 0}, {0, 1, 1, 0, 0}}; cout<<"The minimum distance travelled to meet is "<<minMeetingDistance(distance); return 0; }ผลลัพธ์
The minimum distance travelled to meet is 11
