[LeetCode] 780. Reaching Points

This post is also available in English and alternative languages.

题目大意

• 给定源点 $(x_s, y_s)$ 和目标点 $(x_t, y_t)$
• 定义点的移动方式 $P(x, y) \rightarrow P’(x+y, y)$ 和 $P(x, y) \rightarrow P’(x, x+y)$
• 数据范围：$1 <= sx, sy, tx, ty <= 10^9$

问：源点经过任意次位移，是否有可能到达目标点？

分析

• 从数据范围来看，显然是不允许暴力搜索求解的。因此，这是一道巧妙的数学题（或者脑筋急转弯）。
• 两点都位于第一象限，$x, y$ 均为正整数，因此可以排除所有 $x_s > x_t$ 和 $y_s > y_t$ 的情况。
• 根据移动方式可知，将 $P’(x, y)$ 中的较大值对对方取模，即可退回上个状态 $P(x_0, y_0)$。（这里思路不是很严谨）
  • $P’(x_1, y_0) = P’(x_0 + n\times y_0, y_0)$
  • $P’(x_0, y_1) = P’(x_0, x_0 + n\times y_0)$

求解

递归搜索的思路很简单，但会因为递归次数过多而栈溢出或因为搜索空间过大而超时。

bool reachingPoints(int sx, int sy, int tx, int ty) {
    if (sx > tx || sy > ty)
        return false;
    if (sx == tx && sy == ty)
        return true;
    return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
}

根据点的状态转移关系，我们可以将目标点尽量逼近源点，然后只需对剩下一个轴坐标做判断即可。

bool reachingPoints(int sx, int sy, int tx, int ty) {
    if (sx > tx || sy > ty)
        return false;

    while (sx < tx && sy < ty) {
        if (tx < ty)
            ty %= tx;
        else
            tx %= ty;
    }
                                                        
    // 每次循环只进行一次操作，因此循环结束时分两种情况
    // 1. sx == tx：由于两点 x 不变，合法解只存在 ty = sy + n * sx
    // 2. sy == ty：由于两点 y 不变，合法解只存在 tx = sx + n * sy
    return (sx == tx && (ty - sy) % sx == 0) || (sy == ty && (tx - sx) % sy == 0);
}