স্কোয়ারেল সিমুলেশন (Squirrel Simulation) C++-এ

সমস্যা বিবরণ

একটি গাছ (tree), একটি কাঠবিডাল (squirrel) এবং কিছু বাদাম (nuts) ২D গ্রিডে আছে। কাঠবিডাল একবারে একটি বাদাম নিয়ে গাছে নিয়ে আসতে পারে। চার দিকেই চলতে পারে। সকল বাদাম গাছে নিয়ে আসার ন্যূনতম মোট মুভ (Manhattan distance) বের করতে হবে।

উদাহরণ

Height=5, Width=7, Tree=[2,2], Squirrel=[4,4], Nuts=[[3,0],[2,5]]

আউটপুট: 12

অ্যালগরিদম: গ್ರೀডি + ম্যানহ্যাটন ডিস্ট্যান্স

1. প্রতিটি বাদামের জন্য: গাছ থেকে বাদামের দূরত্ব d = |tree - nut|।
2. সব বাদামের জন্য রাউন্ড ট্রিপ খরচ = 2 * d। মোট total = Σ 2*d।
3. কিন্তু প্রথম বাদামটি কাঠবিডাল আপনার পজিশন থেকে নেবে। সেটি জন্য বাঁচানো খরচ = 2*d - (d + |squirrel - nut|) = d - |squirrel - nut|।
4. সর্বোচ্চ বাঁচানো খরচ (maxDiff) বের করুন।
5. উত্তর = total - maxDiff।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int dist(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>& squirrel, vector<vector<int>>& nuts) {
        int total = 0;
        int maxDiff = INT_MIN;
        for (auto& nut : nuts) {
            int d = dist(tree[0], tree[1], nut[0], nut[1]);
            total += 2 * d;
            int save = d - dist(squirrel[0], squirrel[1], nut[0], nut[1]);
            maxDiff = max(maxDiff, save);
        }
        return total - maxDiff;
    }
};

int main() {
    Solution ob;
    vector<int> tree = {2,2}, squirrel = {4,4};
    vector<vector<int>> nuts = {{3,0}, {2,5}};
    cout << ob.minDistance(5, 7, tree, squirrel, nuts); // 12
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — N = বাদাম সংখ্যা।
• স্থান জটিলতা: O(1) — কনস্ট্যান্ট স্পেস।