Kiểm tra xem có thể di chuyển từ tọa độ đã cho sang tọa độ mong muốn trong C ++ hay không

Giả sử chúng ta có hai tọa độ (sx, sy) và (tx, ty), chúng ta phải kiểm tra xem chúng ta có thể di chuyển từ điểm bắt đầu đến điểm kết thúc hay không. Ở đây, chúng ta có thể di chuyển bằng cách lấy một điểm (x, y) và biến đổi nó thành (x, x + y) hoặc (x + y, y).

Vì vậy, nếu các đầu vào là (1, 1) và (4,5), thì câu trả lời sẽ là đúng, điều này là do chuyển (1,1) thành (2,1), sau đó (3,1), sau đó (4 , 1), sau đó (4,5).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• while tx> sx and ty> sy, do -
  • nếu tx> ty, thì -
    • tx:=tx mod ty
  • Mặt khác
    • ty:=ty mod tx
• return (true khi sx giống với tx AND sy <=ty AND (ty - sy) mod tx giống với 0) OR (sy giống với ty AND x> =sx AND (tx - sx) mod ty là 0)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

1, 1, 4, 5

Đầu ra

1