ถึงจุดใน 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) OR (sy เหมือนกับ ty AND x>=sx AND (tx - sx) mod 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