C++ এ কাঠবিড়ালি সিমুলেশন

একটি গাছ, একটি কাঠবিড়ালি এবং বেশ কয়েকটি বাদাম আছে। অবস্থানগুলি একটি 2D গ্রিডে কোষ দ্বারা প্রতিনিধিত্ব করা হয়। আপনার লক্ষ্য হল কাঠবিড়ালির জন্য ন্যূনতম দূরত্ব খুঁজে বের করা যাতে সব বাদাম সংগ্রহ করা যায় এবং একে একে গাছের নিচে রাখা যায়। কাঠবিড়ালি একবারে সর্বাধিক একটি বাদাম নিতে পারে এবং চারটি দিকে যেতে পারে - উপরে, নীচে, বাম এবং ডানে, সংলগ্ন কোষে। দূরত্বটি চালের সংখ্যা দ্বারা প্রতিনিধিত্ব করা হয়।

সুতরাং, যদি ইনপুটটি উচ্চতা:5 প্রস্থ:7 গাছের অবস্থান:[2,2] কাঠবিড়ালি:[4,4] বাদাম:[[3,0], [2,5]] এর মতো হয়, তাহলে আউটপুট হবে 12 ,

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন calc() সংজ্ঞায়িত করুন, এটি x1, y1, x2, y2,

• ফেরত |x1 - x2| + |y1 - y2|

• একটি ফাংশন সংজ্ঞায়িত করুন minDistance(), এটি উচ্চতা, প্রস্থ, একটি অ্যারে গাছ, একটি অ্যারে বর্গ, একটি 2D অ্যারে বাদাম,

• ret :=0

• maxDiff :=-inf

• আরম্ভ করার জন্য i :=0, যখন i <বাদামের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • dist :=calc(বৃক্ষ[0], গাছ[1], বাদাম[i, 0], বাদাম[i, 1])

  • ret :=ret + 2 * dist

  • maxDiff :=maxDiff এর সর্বোচ্চ এবং 2 * dist - (dist + calc(বাদাম[i, 0], nuts[i, 1], sq[0], sq[1]))

• রিটার্ন 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