ধরুন দুই বা ততোধিক লোকের একটি দল আছে এবং তারা দেখা করতে চায় এবং মোট ভ্রমণ দূরত্ব কমাতে চায়। আমাদের 0 বা 1 মানগুলির একটি 2D গ্রিড রয়েছে, যেখানে প্রতিটি 1 গ্রুপের কারও বাড়ি চিহ্নিত করে। ম্যানহাটন দূরত্বের সূত্র ব্যবহার করে দূরত্ব গণনা করা হয়, তাই দূরত্ব(p1, p2) =|p2.x - p1.x| + |p2.y - p1.y|.
সুতরাং, যদি ইনপুট মত হয়
| 1 | 0 | 0 | 0 | 1 | ৷
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | ৷0 | 0 |
তাহলে আউটপুট হবে 6 হিসাবে ম্যাট্রিক্স থেকে আমরা বুঝতে পারি যে তিনজন মানুষ (0,0), (0,4), এবং (2,2):বিন্দু (0,2) ) হল একটি আদর্শ মিটিং পয়েন্ট, কারণ মোট ভ্রমণ দূরত্ব 2+2+2=6 সর্বনিম্ন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সংজ্ঞায়িত করুন get(), এটি একটি অ্যারে v,
নেবে -
অ্যারে সাজান v
-
i :=0
-
j :=v
এর আকার -
ret :=0
-
যখন আমি
-
ret :=ret + v[j] - v[i]
-
(i 1 দ্বারা বাড়ান)
-
(j 1 দ্বারা কমিয়ে দিন)
-
-
রিটার্ন রিটার্ন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
একটি অ্যারে সারি সংজ্ঞায়িত করুন
-
একটি অ্যারে কল
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i <গ্রিডের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
j শুরু করার জন্য :=0, যখন j <গ্রিডের আকার[0], আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
-
যদি গ্রিড[i, j] অ-শূন্য হয়, তাহলে -
-
সারির শেষে i ঢোকান
-
col
এর শেষে j ঢোকান
-
-
-
-
রিটার্ন get(row) + get(col)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> row;
vector<int> 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 <int> 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;
}
};
main(){
Solution ob;
vector<vector<int>> 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}} আউটপুট
6
