এই সমস্যায়, আমাদেরকে একটি 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
