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 के समान है AND sy <= ty AND (ty - sy) mod tx 0 के समान है) OR (sy, ty के समान है AND tx >= sx AND (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); 
} 

int main() { 
    cout << solve(1, 1, 4, 5); 
    return 0; 
}

इनपुट

1, 1, 4, 5

आउटपुट

1