इस समस्या में, हमें एक 2D बाइनरी ऐरे दिया जाता है यानी इसमें वैल्यूज होती हैं जो या तो 0 या 1 होती हैं, जहां 1 को ग्रुप के एक व्यक्ति के घर के रूप में चिह्नित किया जाता है। और ग्रुप के लोग मिलना चाहते हैं। इसलिए, उन्हें एक कॉमन पॉइंट पर मिलने के लिए उनके द्वारा तय की गई कुल दूरी को न्यूनतम करना होगा। एक वैध मीटिंग पॉइंट कहीं भी हो सकता है लेकिन किसी के घर पर नहीं।
न्यूनतम दूरी खोजने के लिए एक फॉर्मूला बनाया गया है, इसे मैनहट्टन दूरी कहा जाता है, जहां दूरी:
(p1, p2) = |p2.x| + |p2.y - p1.y|।
आइए एक उदाहरण लेते हैं, अवधारणा को स्पष्ट करने के लिए:
उदाहरण
इनपुट:
{10001}
{00000}
{00100}
आउटपुट: 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
