मान लीजिए दो या अधिक लोगों का एक समूह है और वे मिलना चाहते हैं और कुल यात्रा दूरी को न्यूनतम करना चाहते हैं। हमारे पास 0 या 1 के मानों का एक 2D ग्रिड है, जहां प्रत्येक 1 समूह में किसी के घर को चिह्नित करता है। दूरी की गणना मैनहट्टन दूरी सूत्र का उपयोग करके की जाती है, तो distance(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
जब तक i < j, करें −
ret := ret + v[j] - v[i]
(i को 1 से बढ़ाएं)
(j को 1 से घटाएं)
ret लौटाएं
मुख्य विधि से निम्नलिखित करें −
एक ऐरे row परिभाषित करें
एक ऐरे col परिभाषित करें
i := 0 से आरंभ करें, जब i, grid के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j, grid[0] के आकार से कम, अद्यतन करें (j को 1 से बढ़ाएं), करें −
यदि grid[i, j] शून्येतर है, तो −
i को row के अंत में डालें
j को col के अंत में डालें
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