Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सर्वश्रेष्ठ मीटिंग पॉइंट - C++


मान लीजिए दो या अधिक लोगों का एक समूह है और वे मिलना चाहते हैं और कुल यात्रा दूरी को न्यूनतम करना चाहते हैं। हमारे पास 0 या 1 के मानों का एक 2D ग्रिड है, जहां प्रत्येक 1 समूह में किसी के घर को चिह्नित करता है। दूरी की गणना मैनहट्टन दूरी सूत्र का उपयोग करके की जाती है, तो distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|।

तो, यदि इनपुट इस तरह है

10001
00000
00100

तो आउटपुट 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

  1. - C++ कोड: मिलने के बाद न्यूनतम थकान खोजें

    मान लीजिए हमारे पास दो संख्याएं a और b हैं। दो दोस्त OX अक्ष पर स्थिति x = a और x = b पर हैं। प्रत्येक दोस्त रेखा के साथ किसी भी दिशा में एक से अनंत बार आगे बढ़ सकता है। चलने से, एक दोस्त की थकान निम्नलिखित नियमों के अनुसार बदलती है: पहली चाल थकान को 1 से बढ़ाती है, दूसरी चाल 2 से, और इसी तरह। उन दो

  1. C++ में 2-D तल में एक बिंदु का मिरर इमेज ढूंढना C++ में 2-D तल में एक बिंदु का मिरर इमेज ढूंढना

    इस समस्या में, हमें 2-D तल में एक बिंदु P और समीकरण ax + by + c = 0 के बिंदु a, b, c दिए जाते हैं। हमारा कार्य 2-D तल में एक बिंदु का मिरर इमेज ढूंढना है।आइए एक उदाहरण से समस्या को समझते हैं,इनपुटP = (2, 1), a = 1, b = -1, c = 0आउटपुट(1, 2)व्याख्यातल इस तरह दिखता है,समाधान दृष्टिकोणसमस्या को हल करने

  1. C++ में एक बिंदु को दूसरे बिंदु के बारे में घुमाना C++ में एक बिंदु को दूसरे बिंदु के बारे में घुमाना

    मूल बिंदु के बारे में कोण θ पर वामावर्त दिशा में बिंदु X का घुमाव निम्न द्वारा किया जाता है -  X को θ से मूल बिंदु के बारे में वामावर्त घुमाएं: X*polar( 1.0,θ )। यहां, जटिल संख्याओं के लिए polar फ़ंक्शन हेडर फ़ाइल के तहत परिभाषित है और चरण कोण और परिमाण का उपयोग करके एक जटिल संख्या खोजने के ल