मान लीजिए कि दो या दो से अधिक लोगों का समूह है और वे मिलना चाहते हैं और कुल यात्रा दूरी को कम करना चाहते हैं। हमारे पास 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
-
मैं :=0
-
जे:=वी का आकार
-
रिट:=0
-
जबकि मैं <जे, करता हूं -
-
रिट:=रिट + वी[जे] - वी[i]
-
(मैं 1 से बढ़ाइए)
-
(j को 1 से घटाएं)
-
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
एक सरणी पंक्ति परिभाषित करें
-
एक सरणी को परिभाषित करें
-
इनिशियलाइज़ करने के लिए i :=0, जब i <ग्रिड का आकार, अपडेट (i 1 से बढ़ाएँ), करें -
-
इनिशियलाइज़ j :=0 के लिए, जब j <ग्रिड का आकार [0], अपडेट करें (1 से j बढ़ाएँ), करें -
-
अगर ग्रिड [i, j] शून्य नहीं है, तो -
-
पंक्ति के अंत में i डालें
-
कर्नल के अंत में j डालें
-
-
-
-
वापसी प्राप्त करें (पंक्ति) + प्राप्त करें (कॉल)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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