एक पेड़, एक गिलहरी, और कई नट्स हैं। स्थितियों को 2D ग्रिड में सेल द्वारा दर्शाया जाता है। आपका लक्ष्य गिलहरी के लिए सभी नट्स को इकट्ठा करके उन्हें एक-एक करके पेड़ के नीचे रखने के लिए न्यूनतम दूरी ढूंढना है। गिलहरी एक समय में अधिकतम एक नट ले जा सकती है और चार दिशाओं में आगे बढ़ सकती है - ऊपर, नीचे, बाएं, और दाएं, आसन्न सेल तक। दूरी को चालों की संख्या से दर्शाया जाता है।
उदाहरण के लिए, यदि इनपुट ऊंचाई: 5 चौड़ाई: 7 पेड़ की स्थिति: [2,2] गिलहरी: [4,4] नट्स: [[3,0], [2,5]] है, तो आउटपुट 12 होगा।
हल करने की विधि
हम मैनहट्टन दूरी का उपयोग करेंगे:
calc()फ़ंक्शन दो बिंदुओं के बीच मैनहट्टन दूरी की गणना करता है।minDistance()फ़ंक्शन:- ret = 0, maxDiff = -inf।
- प्रत्येक नट के लिए: पेड़ से नट तक की दूरी dist की गणना करें।
- ret += 2 * dist (आना-जाना)।
- maxDiff = max(maxDiff, 2*dist - (dist + गिलहरी से नट की दूरी))।
- ret - maxDiff लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: int calc(int x1, int y1, int x2, int y2){ return abs(x1 - x2) + abs(y1 - y2); } int minDistance(int height, int width, vector<int>& tree, vector<int>& sq, vector<vector>& nuts) { int ret = 0; int maxDiff = INT_MIN; for (int i = 0; i < nuts.size(); i++) { int dist = calc(tree[0], tree[1], nuts[i][0], nuts[i][1]); ret += 2 * dist; maxDiff = max(maxDiff, 2 * dist - (dist + calc(nuts[i][0], nuts[i][1], sq[0], sq[1]))); } return ret - maxDiff; } }; main(){ Solution ob; vector<int> v = {2,2}, v1 = {4,4}; vector<vector<int>> v2 = {{3,0}, {2,5}}; cout << (ob.minDistance(5,7,v, v1, v2)); }
इनपुट
5, 7, {2,2},{4,4}, {{3,0}, {2,5}}
आउटपुट
12