এই সমস্যাতে, আমাদের একটি ২D বাইনারি অ্যারে দেওয়া আছে অর্থাৎ এর মান ০ বা ১, যেখানে ১ কোনো গ্রুপের মেম্বারের হোম হিসেবে মার্ক করা আছে। এবং গ্রুপের মেম্বাররা মিট করতে চায়। তাই তাদের মোট ট্রাভেল ডিস্ট্যান্স মিনিমাইজ করতে হবে একটি কমন মিটিং পয়েন্টে। একটি ভ্যালিড মিটিং পয়েন্ট কোথাও হতে পারে কিন্তু কারো হোমে নয়।
মিনিমাম ডিস্ট্যান্স বের করার জন্য একটি ফর্মুলা তৈরি করা হয়েছে, এটিকে ম্যানহ্যাটান ডিস্ট্যান্স বলা হয়, যেখানে ডিস্ট্যান্স −
(p1, p2) = |p2.x| + |p2.y - p1.y|।
একটি উদাহরণ দিয়ে কনসেপ্ট ক্লিয়ার করি:
উদাহরণ
ইনপুট:
{10001}
{00000}
{00100}
আউটপুট: 6
ব্যাখ্যা − এখানে বেস্ট মিটিং পয়েন্ট (0,2) যা ট্রাভেলড ডিস্ট্যান্স ৬ করে দেয় (২+২+২)।
এখন, এই সমস্যার সমাধান বানাই। এখানে, অ্যারেতে ১ হিসেবে মার্ক করা সব পয়েন্ট থেকে মিডল পয়েন্ট বের করতে হবে। আমরা হরিজেন্টাল এবং ভার্টিক্যাল সেন্টার (মিডল পয়েন্ট) আলাদা আলাদা বের করব। এবং সেটি থেকে সব ১ মার্ক করা পয়েন্টের দূরত্ব বের করব।
অ্যালগরিদম
ধাপ ১: হরিজেন্টাল এবং ভার্টিক্যাল পজিশনগুলোর মান দিয়ে দুটি স্ট্রাকচার বানান যেগুলো ১ হিসেবে মার্ক করা। ধাপ ২: এই দুটি স্ট্রাকচারে মিড পজিশন বের করুন এবং (midx, midy) কে মিটিং পয়েন্ট হিসেবে বিবেচনা করুন। ধাপ ৩: প্রতিটি পয়েন্ট থেকে মিড পর্যন্ত দূরত্ব ক্যালকুলেট করুন। ধাপ ৪: সব দূরত্বের সম রিটার্ন করুন।
উদাহরণ
এই অ্যালগরিদম অনুযায়ী প্রোগ্রাম বানাই −
#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
