การไปถึงจุดหมาย (Reaching Points) ใน C++

ภาพรวมปัญหา

สมมติว่ามีจุดเริ่มต้น (sx, sy) และจุดเป้าหมาย (tx, ty) ต้องการตรวจสอบว่ามีลำดับการเคลื่อนที่จากจุดเริ่มต้นไปจุดเป้าหมายหรือไม่ การเคลื่อนที่: จาก (x, y) สามารถไป (x, x+y) หรือ (x+y, y) ได้

ตัวอย่าง

Start: (1, 1), Target: (4, 5) → true

Path: (1,1) → (2,1) → (3,1) → (4,1) → (4,5)

แนวทางแก้ปัญหา (ย้อนกลับ / Modulo)

• ทำงานย้อนกลับจาก (tx, ty) ไป (sx, sy)
• while tx > sx และ ty > sy: ถ้า tx > ty แล้ว tx %= ty, มิฉะนั้น ty %= tx
• ตรวจสอบเงื่อนไขสุดท้าย: (sx == tx && sy ≤ ty && (ty - sy) % tx == 0) || (sy == ty && tx ≥ sx && (tx - sx) % ty == 0)

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

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

int main() {
    Solution ob;
    cout << (ob.reachingPoints(1, 1, 4, 5));
}

Input

1 1 4 5

Output

1