Đạt điểm trong C ++

Giả sử chúng ta có điểm bắt đầu (sx, sy) và điểm đích (tx, ty), chúng ta phải kiểm tra xem có tồn tại một chuỗi các bước di chuyển từ điểm bắt đầu đến điểm kết thúc hay không. Ở đây di chuyển bao gồm 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)

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

Ví dụ

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

Đầu vào

Đạt điểm trong C ++

Ví dụ

Đầu vào

Đầu ra