इस समस्या में, हमें एक 2D बाइनरी ऐरे दिया जाता है यानी इसमें वे मान होते हैं जो या तो 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