C++-এ গ্রিডের মধ্যে নির্দিষ্ট দিকচালনের সম্ভাব্য মোভ সংখ্যা গণনা

আমাদের দুটি ভেরিয়েবল n এবং m আছে যা n x m আকারের একটি গ্রিড নির্দেশ করে। আর একটি প্রারম্ভিক বিন্দু (x, y) দেওয়া আছে। কিছু মোভ/স্টেপের জোড়া দেওয়া আছে যেমন ((1,1), (2,2)) ইত্যাদি। প্রতিটি জোড়া x এবং y অক্ষে কতটা স্টেপ নেওয়া যাবে তা নির্দেশ করে। লক্ষ্য হল গ্রিডের সীমানা [1,n] x [1,m] এর মধ্যে কতোটা মোভ নেওয়া সম্ভব তা বের করা।

উদাহরণ: n=5, m=4, প্রারম্ভিক অবস্থান (2,2), স্টেপ (1,-1)। একবার স্টেপ নিলে (3,1), আবার নিলে (4,0) — যা অবৈধ কারণ y=-1 বাইরে পড়েছে।

উদাহরণ

ইনপুট: A=3, B=4, x=1, y=1; moves = {{1,1}, {0,-1}}

আউটপুট: ৪

ব্যাখ্যা:

মোভ {1,1} = (2,2) → (3,3) → ৩ স্টেপ
মোভ {0,-1} = (3,2) → (3,1) → ২ স্টেপ
মোট ৪ স্টেপ

ইনপুট: A=4, B=4, x=2, y=2; moves = {{2,1}, {-2,-3}}

আউটপুট: ১

অ্যালগরিদম

1. গ্রিডের আকার A, B এবং প্রারম্ভিক বিন্দু x, y ইনপুট নিন।
2. স্টেপগুলো ভেক্টর vector<pair<int,int>> আকারে সংরক্ষণ করুন।
3. possible_moves(x, y, A, B, move, size) ফাংশন মোট স্টেপ সংখ্যা ফেরত দেবে।
4. possible(int x, int temp_x, int A) ফাংশনটি বর্তমান অবস্থান x, স্টেপের মান temp_x এবং গ্রিডের সীমা A নিয়ে সম্ভাব্য maksimum মোভ সংখ্যা বের করে।
5. যদি temp_x == 0 হয় তবে INT_MAX ফেরত দিন।
6. যদি temp_x > 0 হয় তবে মোভ = |A - x| / temp_x।
7. যদি temp_x < 0 হয় তবে মোভ = |x - 1| / |temp_x|।
8. প্রत्यেক স্টেপের জন্য x এবং y দিকের ন্যূনতম মোভ নিন এবং তা কাউন্টে যোগ করুন।
9. বর্তমান অবস্থান আপডেট করুন এবং পরবর্তী স্টেপে যান।

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

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

int possible(int x, int temp_x, int A) {
    if (temp_x == 0) return INT_MAX;
    if (temp_x > 0) return abs((A - x) / temp_x);
    else return abs((x - 1) / temp_x);
}

int possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        int temp_x = move[i].first;
        int temp_y = move[i].second;
        int check = min(possible(x, temp_x, A), possible(y, temp_y, B));
        count += check;
        x += check * temp_x;
        y += check * temp_y;
    }
    return count;
}

int main() {
    int A = 3, B = 6, x = 3, y = 3;
    vector<pair<int, int>> move = {{2, -1}, {0, 1}, {1, -2}};
    int size = move.size();
    cout << "Count of possible moves in the given direction in a grid are: " 
         << possible_moves(x, y, A, B, move, size);
    return 0;
}

আউটপুট

Count of possible moves in the given direction in a grid are: 3