最短时间访问所有点：理解

Question

我正在尝试解决Leetcode上的一个问题 - "Minimum Time Visiting All Points"。以下是问题的描述 -

在平面上有n个具有整数坐标的点points [i] = [xi，yi]。您的任务是找到访问所有点的最短时间（以秒为单位）。

您可以按照以下规则移动：

一秒钟内，您始终可以沿垂直方向、水平方向各移动一个单位或者对角线移动（即一秒钟内垂直方向和水平方向各移动一个单位）。 您必须按照它们在数组中出现的顺序访问这些点。

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

通过解决一些例子，我能够用以下方法解决这个问题 -

ans += max(abs(points[i][1] - points[i - 1][1]), abs(points[i][0] - points[i - 1][0]))

通过循环 'i' 从1到points.size()，但我无法直观地理解这个问题。有人可以帮助我内化这个问题吗？

- jaya tyagi

---

嗯，你可以在一个“单位时间”内移动x、y或x,y step(步数)，对吧？ - C. R. Ward

Answer 1

由于可以对角线移动，移动次数仅受到最长维度的限制，即 x 或 y。请思考：如果下一个节点离当前节点分别是 +10x 和 -5y，那么需要准确地走 10 步，因为你每次只能沿着 x 移动一步，在克服 x 差异的过程中，将通过对角线移动弥补 y 的差距。

您的代码清晰地表达了这个细节：

如果 dy = abs(points[i][1] - points[i - 1][1])

并且 dx = abs(points[i][0] - points[i - 1][0])

通过取 dx 和 dy 中较大的一个，你可以准确地找到需要多少步就可以到达目标。因为在到达目标的过程中，较小的差距将通过对角线移动来弥补大的差距。 因此，有：

ans += max(dy, dx)

这肯定会为每一对点给出正确的步数。 正如 @flowit 指出的那样，每个连续的点之间的最短路径保证是整个点集的最短路径，因此您将得到正确的总体答案。

- Klaycon

---

需要补充的是：所有3个点（或者如果你将问题推广到N个点，则为N个点）之间的最短路径是所有相邻点之间最短路径的总和。不幸的是，我无法给出数学证明。如果您可以按任意顺序访问这些点，则不再成立。 - flowit

Answer 2

如果有人对此感到困惑，可以在纸上绘制这些点，并手动计算在这些点之间移动的不同方式。您会立即理解，最短距离是X或Y侧中最长的一边，因为斜向移动被视为1，即与X或Y移动相同。

- Chris94549

Answer 3

p=[[1, 1], [3, 4], [-1, 0]]
s=0
for i in range(len(p) - 1):
    l = max(abs(p[i][0] - p[i+1][0]), abs(p[i][1] - p[i+1][1]))
    s = s + l
print(s)

- Abhinandan G

---

请考虑添加一些关于您的代码功能的解释。 - CharonX

Answer 4

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        path = 0
        for i in range(len(points) -1):
            path += max(abs(points[i][0] - points[i+1][0]), abs(points[i][1] - points[i+1][1])) 
        return path

- user2986249

Answer 5

另外，如果有人正在寻找更多信息，我想再补充一件事：

    Key: The time to visit from point (x1, x2) and (y1, y2) is given by
         min(dx, dy) + abs(dx - dy);
         where, dx = abs(x2-x1) , dy = abs(y2-y1)

如果您看到上面的图： 源点：（1，1）
目标点：（3，4）
dx = abs(x2-x1) = 2
dy = abs(y2-y1) = 3
第一步和第二步我们是斜着走的。
我们所采取的第三步实际上等于（dy-dx）
（请阅读注释：正方形的边长= dx）。
因此，我们首先尽可能地斜着走，然后再通过垂直/水平移动来到达目标点。

- Mazhar MIK

Answer 6

如果有人还感到困惑，那么基本的核心逻辑是：

max_distance = max（abs（x2-x1），abs（y2-y1））

这个 max_distance 数字给出了从点 1 = [x1，y1] 到点 2 = [x2，y2] 的秒数。

然后，您重复相同的逻辑，针对点 2 和点 3 等等。

最后，将所有的 max_distances 相加，这应该会给你答案。

- Vasantha Bhanu