हम दो चर n और m हैं जो n x m आकार के ग्रिड का प्रतिनिधित्व करते हैं और प्रारंभिक बिंदु x, y से शुरू करते हैं।
कदमों/चालों के जोड़े भी दिए गए हैं जिन्हें चाल ((1,1), (2,2)) आदि के रूप में ग्रिड के अंदर ले जाया जा सकता है। चालों की प्रत्येक जोड़ी x,y अक्ष में उठाए गए कदमों की इकाई का प्रतिनिधित्व करती है। लक्ष्य कुल चरणों का पता लगाना है जो ग्रिड के अंदर सीमाओं के भीतर पार करने के लिए उठाए जा सकते हैं [1,n] एक्स [1, मी] यदि n 5 है और m 4 है और वर्तमान स्थिति 2,2 है और चुना गया चरण है ( 1,-1) तो एक बार इस कदम को उठाने से (3,1) हो जाएगा, इस कदम को फिर से उठाने पर (4,-1) हो जाएगा जो मान्य नहीं है क्योंकि -1 सीमा से बाहर है।
आइए उदाहरणों के साथ समझते हैं
इनपुट - ए =3, बी =4, एक्स =1, वाई =1; चालें ={ 1, 1}, { 0, -1}
आउटपुट − ग्रिड में दी गई दिशा में संभावित चालों की संख्या है − 4
स्पष्टीकरण -
Choosing move {1,1} = → (2,2) → (3,3) - 3 steps
Choosing move {0,-1} = → (3,2) → (3,1) - 2 steps
Total 4 steps. इनपुट - ए =4, बी =4, एक्स =2, वाई =2; चालें ={ 2, 1 }, { -2, -3 }
आउटपुट - ग्रिड में दी गई दिशा में संभावित चालों की संख्या है - 1
स्पष्टीकरण
Choosing move {2,1} = → (4,3) - 1 step1
Choosing move {-2,-3} = → (2,0) X out of bound
Total 1 step नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम जोड़ी के रूप में चरणों का प्रतिनिधित्व करने वाला एक वेक्टर बनाएंगे
-
AXB ग्रिड को निरूपित करने के लिए चर A,B और आरंभिक बिंदु के लिए x,y लें।
-
एक वेक्टर लें जिसमें पूर्णांक जोड़े होते हैं (वेक्टर <जोड़ी
-
फ़ंक्शन संभव_मूव्स (इंट एक्स, इंट वाई, इंट ए, इंट बी, वेक्टर<जोड़ी<इंट, इंट>> मूव, इंट साइज) सभी चर और चाल लेता है और ग्रिड में दी गई दिशा में संभावित चालों की गिनती देता है।
-
फ़ंक्शन संभव (int x, int temp_x, int A) निर्देशांक की वर्तमान स्थिति x के रूप में लेता है, इसी समन्वय मान को temp_x के रूप में ले जाता है और उस समन्वय के लिए ग्रिड की सीमा A के रूप में लेता है।
-
अब अगर temp_x 0 है तो वापसी मान को अधिकतम बनाने के लिए INT_MAX लौटाएं।
-
यदि temp_x> 0 है तो A तक पहुँचने के लिए चालें होंगी | ए-एक्स |/temp_x
-
वरना 1 चाल की ओर बढ़ना होगा | x-1 |/temp_x.
-
संबंधित गणना की गई चालें लौटाएं।
-
संभव_मूव्स () के अंदर, प्रारंभिक गणना 0 के रूप में लें।
-
i=0 से i<आकार तक लूप के लिए उपयोग करते हुए ट्रैवर्स वेक्टर।
-
वर्तमान जोड़ी से निर्देशांक निकालें जैसे temp_x=move[i].first और temp_y=move[i].second.
-
संभव () फ़ंक्शन का उपयोग करके न्यूनतम संभव चालों के रूप में परिवर्तनीय जांच करें।
-
चेक में न्यूनतम मूल्य कुल चरणों की गणना के लिए जोड़ा जाएगा।
-
अब जबकि हमने चेक चुना है, x और y को चेक से अपडेट करें।
-
अंत में हम एक ग्रिड में दी गई दिशा में संभावित चालों की कुल संख्या प्राप्त करेंगे
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#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 = count + check;
x = x + check * temp_x;
y = 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