जाँच करें कि क्या C++ में दिए गए निर्देशांक से वांछित निर्देशांक में जाना संभव है

मान लीजिए कि हमारे पास दो निर्देशांक (sx, sy), और (tx, ty) हैं, हमें जांचना है कि हम प्रारंभिक बिंदु से अंत बिंदु तक जा सकते हैं या नहीं। यहां हम एक बिंदु (x, y) लेने और इसे (x, x+y) या (x+y, y) में बदलने के लिए चल सकते हैं।

तो अगर इनपुट (1, 1) और (4,5) हैं, तो उत्तर सही होगा, ऐसा इसलिए है क्योंकि (1,1) से (2,1), फिर (3,1), फिर (4 ,1), फिर (4,5)।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• जबकि tx> sx और ty> sy, करते हैं −
  • यदि tx> ty, तो −
    • tx :=tx mod ty
  • अन्यथा
    • ty:=ty mod tx
• वापसी (सच है जब sx tx और sy <=ty और (ty - sy) mod tx के समान है 0) या (sy ty और x> =sx और (tx - sx) mod ty के समान है है 0)

उदाहरण (C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
bool solve(int sx, int sy, int tx, int ty) {
   while(tx > sx && ty > sy){
      if(tx > ty){
         tx %= ty;
      }else ty %= tx;
   }
   return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
}
main(){
   cout << solve(1,1,4,5);
}

इनपुट

1, 1, 4, 5

आउटपुट

1