Kiểm tra di chuyển từ tọa độ nguồn đến đích (Reaching Points) trong C++

Cho tọa độ bắt đầu (sx, sy) và tọa độ đích (tx, ty). Từ một điểm (x, y), ta chỉ được phép di chuyển sang (x, x+y) hoặc (x+y, y). Kiểm tra có thể đến đích hay không.

Ví dụ

Đầu vào: (1, 1) -> (4, 5)

Đầu ra: True (Có thể)

Lộ trình: (1,1) -> (2,1) -> (3,1) -> (4,1) -> (4,5).

Phân tích & Thuật toán tối ưu (Ngược - Reverse Engineering)

Thay vì tìm đường đi từ (sx, sy) -> (tx, ty) (nhanh chóng phát sinh nhánh), ta **ngược từ đích về nguồn**.

Tại điểm (tx, ty) (giả sử tx, ty > 0):

• Nếu tx > ty: Bước trước chắc chắn là (tx - ty, ty) (vì chỉ có phép +x mới làm tăng x). Thay vì trừ lần lượt, ta dùng modulo: tx %= ty.
• Nếu ty > tx: Bước trước là (tx, ty - tx) => ty %= tx.
• Dừng khi tx <= sx hoặc ty <= sy.

Cuối cùng kiểm tra điều kiện khớp:

• Nếu tx == sx: Cần ty >= sy và (ty - sy) % tx == 0 (có thể cộng sx nhiều lần để ra ty).
• Nếu ty == sy: Cần tx >= sx và (tx - sx) % ty == 0.

Chương trình C++ (Độ phức tạp O(log max(tx, ty)))

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

bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy) {
        if (tx > ty) tx %= ty;
        else ty %= tx;
    }
    
    if (tx == sx && ty == sy) return true;
    if (tx == sx) return ty > sy && (ty - sy) % tx == 0;
    if (ty == sy) return tx > sx && (tx - sx) % ty == 0;
    
    return false;
}

int main() {
    cout << boolalpha;
    cout << "(1,1) -> (4,5): " << reachingPoints(1, 1, 4, 5) << endl; // true
    cout << "(1,1) -> (2,2): " << reachingPoints(1, 1, 2, 2) << endl; // false
    cout << "(3,7) -> (10, 21): " << reachingPoints(3, 7, 10, 21) << endl; // true
    return 0;
}

Đầu ra

(1,1) -> (4,5): true
(1,1) -> (2,2): false
(3,7) -> (10, 21): true