सी ++ में गिलहरी सिमुलेशन

एक पेड़, एक गिलहरी, और कई नट हैं। स्थितियों को 2डी ग्रिड में कोशिकाओं द्वारा दर्शाया जाता है। आपका लक्ष्य गिलहरी के लिए सभी नटों को इकट्ठा करने और उन्हें एक-एक करके पेड़ के नीचे रखने के लिए न्यूनतम दूरी का पता लगाना है। गिलहरी एक समय में केवल एक अखरोट ले सकती है और चार दिशाओं में - ऊपर, नीचे, बाएँ और दाएँ, आसन्न कोशिका में जा सकती है। दूरी चालों की संख्या से प्रदर्शित होती है।

इसलिए, यदि इनपुट ऊँचाई:5 चौड़ाई:7 पेड़ की स्थिति:[2,2] गिलहरी:[4,4] नट:[[3,0], [2,5]] जैसा है, तो आउटपुट 12 होगा ,

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन कैल्क () को परिभाषित करें, इसमें x1, y1, x2, y2,

  लगेगा

• वापसी |x1 - x2| + |y1 - y2|

• फ़ंक्शन minDistance() को परिभाषित करें, इसमें ऊंचाई, चौड़ाई, एक सरणी वृक्ष, एक सरणी वर्ग, एक 2D सरणी नट,

• रिट:=0

• मैक्सडिफ:=-इन्फ

• इनिशियलाइज़ करने के लिए i:=0, जब i <नट का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • जिला:=कैल्क (पेड़ [0], पेड़ [1], नट [i, 0], नट [i, 1])

  • रिट:=रिट + 2 * जिला

  • मैक्सडिफ:=मैक्सडिफ और 2 * डिस्ट का अधिकतम - (डिस्ट + कैल्क (नट्स [i, 0], नट्स [i, 1], वर्ग [0], वर्ग [1]))

• रिटर्न रिट - मैक्सडिफ

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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