ตรวจสอบการเคลื่อนที่จากพิกัดหนึ่งไปอีกพิกัดใน C++

ปัญหา

ได้รับพิกัดเริ่มต้น (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)

อัลกอริธึม (ย้อนกลับจากเป้าหมาย)

ใช้ Modulo เพื่อลดค่าทีละขั้น:

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)

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

bool canReach(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);
}

int main() {
    cout << canReach(1, 1, 4, 5);  // 1 (true)
    return 0;
}