মনে করুন, একটি শুরুর বিন্দু (sx, sy) এবং একটি লক্ষ্য বিন্দু (tx, ty) দেওয়া আছে। আমাদের যাচাই করতে হবে যে, শুরুর বিন্দু থেকে লক্ষ্য বিন্দুতে যাওয়ার কোনো পথ আছে কিনা। এখানে প্রতিটি চলে (x, y) বিন্দুটিকে অথবা (x, x+y) অথবা (x+y, y)-এ রূপান্তর করা যায়।
যেমন, (1, 1) এবং (4, 5) হলে, উত্তর হবে true। কারণ (1,1) -> (2,1) -> (3,1) -> (4,1) -> (4,5)।
সমাধানের ধাপসমূহ
- যখন tx > sx এবং ty > sy
- যদি tx > ty হয়, tx := tx % ty
- অন্যথায় ty := ty % tx
- রিটার্ন করুন: (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0)
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: bool reachingPoints(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(){ Solution ob; cout << (ob.reachingPoints(1,1,4,5)); }
ইনপুট
1 1 4 5
আউটপুট
1
