ในปัญหานี้ เราได้รับอาร์เรย์ไบนารี 2 มิติ นั่นคือมีค่าที่เป็น 0 หรือ 1 โดยที่ 1 ถูกทำเครื่องหมายว่าเป็นบ้านของบุคคลในกลุ่ม และคนในกลุ่มต้องการพบปะ ดังนั้นพวกเขาจึงต้องลดระยะทางทั้งหมดที่เดินทางโดยพวกเขาเพื่อพบกันที่จุดร่วม จุดนัดพบที่ถูกต้องจะอยู่ที่ใดก็ได้แต่ไม่สามารถอยู่ที่บ้านใครได้
สำหรับสูตรการหาระยะทางต่ำสุด ให้ตั้งชื่อว่าระยะทางแมนฮัตตันโดยที่ระยะทาง −
(p1, p2) =|p2.x| + |p2.y - p1.y|.
มาดูตัวอย่างกันเพื่อให้แนวคิดชัดเจน
ตัวอย่าง
Input:
{10001}
{00000}
{00100}
Output: 6 คำอธิบาย − จุดนัดพบที่ดีที่สุดคือ (0,2 ) ซึ่งทำให้ระยะทางที่เดินทางเท่ากับ 6 (2+2+2)
ตอนนี้ มาสร้างวิธีแก้ปัญหาสำหรับปัญหานี้กัน ในที่นี้ เราต้องหาจุดกึ่งกลางจากจุดทั้งหมดที่ทำเครื่องหมายเป็น 1 ในอาร์เรย์ เราจะทำสิ่งนี้โดยหาจุดศูนย์กลางแนวนอนและแนวตั้ง (จุดกลาง) แยกกัน และผมกำลังหาระยะทางของจุดจากจุดที่ทำเครื่องหมายไว้ทั้งหมด 1 จุด
อัลกอริทึม
Step 1 : Create two structures with the values of horizontal and vertical positions of the points Marked one. Step 2 : In both this structures, find the mid positions and treat (midx, midy) it as the meeting point. Step 3 : Calculate the distance of each point it to the mid. Step 4 : return the sum of all distances.
ตัวอย่าง
มาสร้างอัลกอริทึมตามอัลกอริทึมนี้กันเถอะ -
#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
