C ++で、指定された座標から目的の座標に移動できるかどうかを確認します

2つの座標（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
• return（sxがtxANDsyと同じ場合はtrue<=ty AND（ty --sy）mod txは0と同じ）OR（syはty AND x> =sx AND（tx --sx）modtyと同じは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