C++-এ সেরা মিটিং পয়েন্ট (Best Meeting Point) বের করা

ধরি দুজন বা অধিক মানুষের একটি গোষ্ঠী আছে যারা মিলতে চায় এবং মোট ভ্রমণ দূরত্ব ন্যূনতম করতে চায়। আমাদের একটি 2D গ্রিড আছে যার মান 0 বা 1, যেখানে 1 মানে কোনো কাউকে বাসা। দূরত্ব ম্যানহ্যাটান ডিস্ট্যান্স (Manhattan Distance) দিয়ে বের করা হয়: distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|।

উদাহরণস্বরূপ, গ্রিড:

1	0	1
0	0	0
0	1	0

আউটপুট হবে 6 কারণ তিনজন মানুষ থাকে (0,0), (0,4), এবং (2,2)-এ। পয়েন্ট (0,2) আদর্শ মিটিং পয়েন্ট, কারণ মোট দূরত্ব 2+2+2=6 ন্যূনতম।

সমাধানের ধাপসমূহ

get(v) ফাংশন:
- v সর্ট করা
- i := 0, j := v.size()-1, ret := 0
- যখন i < j:
  - ret += v[j] - v[i]
  - i++; j--
- ret ফেরত
মেইন মেথড:
- দুটি অ্যারে row এবং col
- গ্রিডের সব সেল (i,j) জন্য যদি grid[i][j] != 0: row.push_back(i), col.push_back(j)
- ফেরত: get(row) + get(col)

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minTotalDistance(vector>& grid) {
        vector row;
        vector col;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
        return get(row) + get(col);
    }
    int get(vector v) {
        sort(v.begin(), v.end());
        int i = 0;
        int j = v.size() - 1;
        int ret = 0;
        while (i < j) {
            ret += v[j] - v[i];
            i++;
            j--;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
    cout << (ob.minTotalDistance(v));
}

ইনপুট

{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}