> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/780-reaching-points.md).

# 780 Reaching Points

## 780. [Reaching Points](https://leetcode.com/problems/reaching-points/description/)

## 1. Question

A move consists of taking a point`(x, y)`and transforming it to either`(x, x+y)`or`(x+y, y)`.

Given a starting point`(sx, sy)`and a target point`(tx, ty)`, return`True`if and only if a sequence of moves exists to transform the point`(sx, sy)`to`(tx, ty)`. Otherwise, return`False`.

```
Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5

Output: True

Explanation:

One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2

Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1

Output: True
```

**Note:**

* `sx, sy, tx, ty`will all be integers in the range`[1, 10^9]`.

## 2. Implementation

**(1) BFS (TLE)**

```java
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) {
            return false;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {sx, sy});

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curPoint = queue.remove();
                int x = curPoint[0], y = curPoint[1];

                if (x == tx && y == ty) {
                    return true;
                }

                if (x + y <= tx) {
                    queue.add(new int[] {x + y, y});
                }

                if (x + y <= ty) {
                    queue.add(new int[] {x, x + y});
                }
            }
        }
        return false;
    }
}
```

**(2) Math**

思路：看[解析](https://leetcode.com/problems/reaching-points/discuss/114726/C++-Simple-iterative.)

```java
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx < tx && sy < ty) {
            if (tx > ty) {
                tx %= ty;
            }
            else {
                ty %= tx;
            }
        }

        if (sx == tx) {
            return (ty - sy) % sx  == 0;
        }
        else if (sy == ty) {
            return (tx - sx) % sy == 0;
        }
        else {
            return false;
        }
    }
}
```

## 3. Time & Space Complexity

Math: 时间复杂度O(max(tx, ty)), 空间复杂度O(1)