从到坐标的可能路径

Question

我最近参加了一次面试，我的算法只通过了所有测试用例，只有一个除外，我不明白为什么。我需要解决的问题是：

给定二维网格中的一个站立点(a,b) 是否有可能到达目的地点(x, y)。他唯一能做的操作就是从某个点(a,b)移动到点(a+b,b)或者(a,a+b)。

我试着用gcd解决了。例如如果 gcd(a,b) = gcd(x,y) 那么它是可能的，否则不是。直觉是如果 k 是 a 和 b 的 gcd。然后，k 也会除以 (a+b)。我使用以下算法计算 gcd：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

编辑：此外，数字 a、b、x 和 y 都是正整数。

Answer 1

GCD(3,7) = GCD(7,3) 但彼此都无法访问。你的条件是必要但不充分的。

请注意，每个点都有一个唯一的可能前导。 IE。对于点 (a,b) 如果 a>b 则前驱是 (a-b,b) 否则前驱是 (a, b-a).

Answer 2

您现在有 2 个关于 post 的问题：

GCD 是必要条件，但不是充分条件。

正确，如果 a=b，则 (x, y) 是可达的当且仅当 GCD(x, y) = a = b。但是，这并不适用于所有问题对。简单的反例是试图从 (N,1) 到达 (1, N)，其中 N>1。另一个是 (2, 3) => (4, 5).

那么，让我们进入定性部分："I can't figure out ..."。我怀疑问题出在您看到欧几里德算法与加法步骤之间的相似之处。更强大的是，link中的"backwards"算法表明欧几里得算法适用。

它可以，在某种程度上，但不像您尝试使用它那样简单和普遍。将问题视为笛卡尔平面中正整数点阵的图形。允许的操作（有向边）定义了如何从一个点移动到另一个点。

这里的关键术语是定向：一旦你"moved"从一个起点到在你的系统中定义GCD的起点，你就not 可以自由地追溯这些步骤。您在图表 space.

中向前或向后移动

例如，虽然您的向后转换允许您从 (4, 1) 移动到 (1, 1) 或从 (1, 4) 移动到 (1, 1)，但您不能用它来得出从 (4, 1) 到 (1, 4) 的路径：其中一半的移动方向是不允许的。

这是否有助于消除困惑？

Possible Path from to Co-ordinates