机器人能到达点(x，y)吗？

Question

我在一次面试中遇到了这个问题&我找不到解决方案的正确算法，所以我在这里张贴这个问题：

有一个机器人可以在两种方式之一的协调平面上移动：

如果机器人当前的位置是(x，y)，那么机器人可以移动等于x&y之和，如果方向是这样的：

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

现在，给定初始点(x1，y1)和目标点(x2，y2)，您需要编写一个程序来检查机器人是否能够通过任意次数的移动到达目的地。

注: x1，y1，x2，y2 > 0

解释：

1. 假设机器人的初始点为(2,3)，而初始点为(7,5)。 在这种情况下，结果是肯定的，因为机器人可以走这条路： (2,3) -> (2，2+3) => (2，5) (2,5) -> (2+5，5) => (7,5)
2. 假设机器人的初始点为(2,3)，而初始点为(4,5)。 结果在这种情况下，机器人无论走哪条路都不能达到(4,5)。

Answer 1

天真的蛮力方法

一种方法是递归地探索每一个可能的移动，直到您到达目标。

需要考虑的是，机器人可以无限期地移动(永远不会到达目标)，所以您需要一个结束情况，这样功能就完成了。幸运的是，在x和y轴上的位置总是在增加，所以当x坐标或y坐标大于目标时，您可以放弃探索这条路径。

所以，就像：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)

它的作用是：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

一个限制是，这不适用于负坐标-不确定这是否是一个要求，只要让我知道它是否是，我将适应答案。

细菌追踪

另一方面，如果不允许负协调，那么我们也可以将其作为Dave suggests来处理。这样做的效率要高得多，因为意识到机器人只有一种方法可以到达每个坐标。

该方法依赖于能够确定我们前进的方向:增加x坐标还是y坐标。我们可以通过选择两个坐标中较大的一个来确定最后一次改变的坐标。以下证据保证情况是这样的。

状态变化的可能性是：

1. (a, b) => (a+b, b)       a x-coordinate change

和,

2. (a, b) => (a, a+b)       a y-coordinate change

如果(1)，x坐标现在更大，因为：

    a > 0
a + b > b  (add b to both sides)

同样，由于b也是> 0，我们可以推断a+b是> a。

现在我们可以从目标开始，问:是哪个坐标引导我们来到这里？答案很简单。如果x坐标大于y坐标，则从x坐标减去y坐标，否则从y坐标减去x坐标。

也就是说，对于一个坐标，如果是(x,y)，如果是x > y，那么我们来自(x-y,y)，否则是(x,y-x)。

第一段代码现在可以修改为：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if target[0] < pos[0] or target[1] < pos[1]: 
        return False
    x, y = target
    return can_reach_target(pos, (x-y,y) if x > y  else (x,y-x))

如预期的那样工作：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

时差

>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722

因此，您可以看到，在这两种情况下，backtracker的速度都快了近三倍。

Answer 2

向后走。我假设起始坐标是正的。假设您想知道(a，b)的起点是否与(x，y)的端点兼容。从(x，y)到(x-y，y)或(x，y-x)后退一步。如果x>y选择前者，否则选择后者。

Answer 3

我同意戴夫的观点，倒退是一种有效的方法。如果只有正坐标是合法的，那么每个坐标最多只有一个有效的父坐标。这可以让你在没有组合爆炸的情况下向后工作。

下面是一个示例实现：

def get_path(source, destination):
    path = [destination]
    c,d = destination
    while True:
        if (c,d) == source:
            return list(reversed(path))
        if c > d:
            c -= d
        else:
            d -= c
        path.append((c,d))
        if c < source[0] or d < source[1]:
            return None

print(get_path((1,1), (1,1)))
print(get_path((2,3), (7,5)))
print(get_path((2,3), (4,5)))
print(get_path((1,1), (6761, 1966)))
print(get_path((4795, 1966), (6761, 1966)))

结果：

[(1, 1)]
[(2, 3), (2, 5), (7, 5)]
None
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (6, 5), (11, 5), (16, 5), (21, 5), (26, 5), (31, 5), (36, 5), (41, 5), (46, 5), (46, 51), (46, 97), (143, 97), (143, 240), (383, 240), (623, 240), (863, 240), (863, 1103), (863, 1966), (2829, 1966), (4795, 1966), (6761, 1966)]
[(4795, 1966), (6761, 1966)]

附录:我沿途提出的一些可能有助于找到O(1)解决方案的意见：

• (a，b)可从(1,1)处到达当且仅当a和b是相互作用的。
• 如果a和b有一个共同的因子，那么(a，b)的所有子元素也有这个共同因子。等价地，如果存在从(a，b)到(c，d)的路径，则对于任何正整数n也有从(n*a，n*b)到(n*c，n*d)的路径。
• 如果a和b是相互作用的，而不是(1,1)，那么就有无穷多个从(a，b)处不可到达的坐标。通过选择(a，b)作为起点，您实际上是将自己限制在由(1,1)构成的树的某个子分支上。您永远无法到达(a，b)的任何同级分支，其中存在无穷多个坐标。