# The naive solution got TLE

`100 / 190 test cases passed.typedef pair<int, int> ii;class Solution {public:    bool reachingPoints(int sx, int sy, int tx, int ty) {        queue<ii> Q;        Q.emplace(sx, sy);        set<ii> seen;        seen.emplace(sx, sy);        while (!Q.empty()) {            auto [x, y] = Q.front(); Q.pop();            if (x == tx && y == ty) return true;            int x_plus_y = x + y;            if (x_plus_y <= tx && !seen.count(make_pair(x_plus_y, y))) {                Q.emplace(x_plus_y, y);                seen.emplace(x_plus_y, y);            }            if (x_plus_y <= ty && !seen.count(make_pair(x, x_plus_y))) {                Q.emplace(x, x_plus_y);                seen.emplace(x, x_plus_y);            }        }        return false;    }};`

# Solve it backward

Since our begin point can only be a number greater than 1, we can solve the problem backward. Detail can be seen from the following figure. A naive way to solve the problem backward, we still get TLE, although we can pass more test cases.

`156 / 190 test cases passed.class Solution {public:    bool reachingPoints(int sx, int sy, int tx, int ty) {        while (tx > 0 && ty > 0) {            if (tx == sx && ty == sy) return true;            if (tx > ty) {                tx -= ty;            }            else if (tx == ty) return false;            else ty -= tx;        }        return false;    }};`
`class Solution {public:    bool reachingPoints(int sx, int sy, int tx, int ty) {        while (tx > 0 && ty > 0) {            if (tx == sx && ty == sy) return true;            if (tx > ty) {                if (sx < ty) tx %= ty;                // tx will be greater than ty, we can not change ty, so we have to make sure ty == sy                 else return (ty == sy && tx >= sx && (tx - sx) % ty == 0);            }            else if (tx == ty) return false;            else {                                if (sy < tx) ty %= tx;                // In order to make the following case can get passed, we have to add the ty >= sy                 //  3, 7, 3, 4                else return (tx == sx && ty >= sy && (ty - sy) % tx == 0);            }                        }        return false;    }};`