C++で開始座標から目標座標への移動が可能かどうかを判定する方法

2つの座標 (sx, sy) と (tx, ty) が与えられたとき、開始点から終点へ移動できるかどうかを判定する問題を考えてみましょう。ここでいう「移動」とは、ある点 (x, y) を (x, x+y) または (x+y, y) のいずれかに変換する操作のことです。

例えば、入力が (1, 1) と (4, 5) の場合、答えは true（移動可能）となります。これは、(1, 1) → (2, 1) → (3, 1) → (4, 1) → (4, 5) という順番で移動できるためです。

アルゴリズムの考え方

この問題は、ユークリッドの互除法と同じ発想で逆算的に解くのが効果的です。前進する操作は座標を増やすだけなので、目標座標側から剰余を取っていくことで、開始点に一致させられるかを効率よく調べられます。手順は以下の通りです。

• tx > sx かつ ty > sy の間、次の処理を繰り返します。
  • tx > ty の場合：tx := tx mod ty
  • それ以外の場合：ty := ty mod tx
• ループを抜けたら、次の条件のいずれかを満たしていれば true を返します。
  • sx == tx かつ sy <= ty かつ (ty − sy) mod tx == 0
  • sy == ty かつ tx >= sx かつ (tx − sx) mod ty == 0

この方法なら、座標の値が非常に大きい場合でも、単純に1ステップずつシミュレーションする方式と比べて大幅に高速に判定できます。

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

出力が 1（true）となっており、(1, 1) から (4, 5) への移動が可能であることが確認できました。