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, do −
  동안
  • tx> ty이면 -
    • tx :=tx 모드 ty
  • 그렇지 않으면
    • ty :=ty 모드 tx
• return(sx가 tx와 같을 때 참 AND sy <=ty AND (ty - sy) mod tx가 0과 같을 때) OR (sy가 ty와 같을 때 AND x>=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);
}
main(){
   cout << solve(1,1,4,5);
}

입력

1, 1, 4, 5

출력

1