1.题目基本信息

1.1.题目描述

给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。

从点 (x, y) 可以转换到 (x, x+y) 或者 (x+y, y)。

1.2.题目地址

https://leetcode.cn/problems/reaching-points/description/

2.解题方法

2.1.解题思路

反向计算

假设从状态(x,y)转到(tx,ty)；第一种转换方法：x=tx,x+y=ty，则x=tx,y=ty-tx（此时必须满足ty>tx）；第二种转换方法x+y=tx,y=ty，则x=tx-ty,y=ty（此时必须满足tx>ty）。

根据这两种情况，可以知道如果tx=ty，则没有上一个状态，如果tx>ty，可以找到的上一个状态为(tx-ty,ty)，如果tx<ty，上一个状态为(tx,ty-tx)。

又当tx>ty(ty>tx)时，可以一直更新直到txty)，所以更新时可以直接tx mod ty(ty mod tx)。

如果更新中途遇到(sx,sy)，则说明可以找到终点，否则说明不能找到终点

2.2.解题步骤

第一步，使用mod运算进行移动

第二步，判断移动后的状态是否合法

3.解题代码

python代码

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        # 思路：反向计算。假设从状态(x,y)转到(tx,ty)；第一种转换方法：x=tx,x+y=ty，则x=tx,y=ty-tx（此时必须满足ty>tx）；第二种转换方法x+y=tx,y=ty，则x=tx-ty,y=ty（此时必须满足tx>ty）；根据这两种情况，可以知道如果tx=ty，则没有上一个状态，如果tx>ty，可以找到的上一个状态为(tx-ty,ty)，如果tx<ty，上一个状态为(tx,ty-tx)。又当tx>ty(ty>tx)时，可以一直更新直到tx<ty(tx>ty)，所以更新时可以直接tx mod ty(ty mod tx)。如果更新中途遇到(sx,sy)，则说明可以找到终点，否则说明不能找到终点
        # 第一步，使用mod运算进行移动
        x, y = tx, ty
        while x > sx and y > sy:
            if x > y:
                x %= y
            else:
                y %= x
        # 第二步，判断移动后的状态是否合法
        if x == sx and y == sy:
            return True
        elif x == sx:
            # 通过k步移动回到起点
            return y > sy and (y - sy) % sx == 0
        elif y == sy:
            return x > sx and (x - sx) % sy == 0
        else:
            return False

4.执行结果