ग्रिड में दी गई दिशा में संभावित चालों की गणना करने का C++ प्रोग्राम

समस्या विवरण

हमें n x m आकार का ग्रिड और प्रारंभिक बिंदु (x, y) दिया गया है। साथ ही चालों/कदमों के जोड़े दिए गए हैं जैसे (1,1), (2,2) आदि। प्रत्येक जोड़ा x और y अक्ष में कदम की इकाइयों को दर्शाता है। लक्ष्य ग्रिड की सीमाओं [1,n] x [1,m] के भीतर ली जा सकने वाली कुल चालों की संख्या ज्ञात करना है।

उदाहरण

इनपुट: A = 3, B = 4, x = 1, y = 1; moves = {{1,1}, {0,-1}}

आउटपुट: 4

व्याख्या:

• चाल {1,1} चुनें: (2,2) → (3,3) — 3 कदम
• चाल {0,-1} चुनें: (3,2) → (3,1) — 2 कदम
• कुल 4 कदम

इनपुट: A = 4, B = 4, x = 2, y = 2; moves = {{2,1}, {-2,-3}}

आउटपुट: 1

व्याख्या:

• चाल {2,1}: (4,3) — 1 कदम
• चाल {-2,-3}: (2,0) — सीमा से बाहर
• कुल 1 कदम

दृष्टिकोण

चरणों को pair<int,int> के वेक्टर के रूप में दर्शाएँ। बिंदु (x,y) से पार करना शुरू करें। वेक्टर से एक चरण चुनें और दोनों दिशाओं (x अक्ष और y अक्ष) में लिए गए मान का न्यूनतम चुनें। न्यूनतम मान अधिक चालों की अनुमति देगा।

किसी विशेष दिशा में जाने के लिए:

• यदि वर्तमान स्थिति x > n (या y > m) है तो n (या m) तक पहुँचने के लिए चालों की संख्या = |n - cur| / step
• यदि कम है तो 1 तक पहुँचने के लिए चालें = |cur - 1| / step

एल्गोरिदम

1. चर A, B ग्रिड के लिए और x, y प्रारंभिक बिंदु के लिए लें
2. चालों का वेक्टर लें vector<pair<int,int>>
3. फंक्शन possible(int x, int step, int limit):
   • यदि step == 0 तो INT_MAX लौटाएँ
   • यदि step > 0 तो abs((limit - x) / step) लौटाएँ
   • अन्यथा abs((x - 1) / step) लौटाएँ
4. फंक्शन possible_moves() में:
   • प्रारंभिक गणना = 0
   • प्रत्येक चाल के लिए check = min(possible(x, dx, A), possible(y, dy, B))
   • count += check
   • x += check * dx, y += check * dy से स्थिति अपडेट करें
5. कुल गणना लौटाएँ

C++ कार्यान्वयन

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

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

int possible_moves(int x, int y, int A, int B, vector<pair<int,int>> moves) {
    int count = 0;
    for (auto [dx, dy] : moves) {
        int check = min(possible(x, dx, A), possible(y, dy, B));
        count += check;
        x += check * dx;
        y += check * dy;
    }
    return count;
}

int main() {
    int A = 3, B = 6, x = 3, y = 3;
    vector<pair<int,int>> moves = {{2,-1}, {0,1}, {1,-2}};
    cout << "Count: " << possible_moves(x, y, A, B, moves);
    return 0;
}

आउटपुट

Count: 3