c++ - 访问所有点的最短时间 : Understanding

Question

我试图解决 leetcode 中的一个问题——“访问所有点的最短时间”。下面是问题的描述——

在一个平面上有 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() 但我无法直观地理解这个问题。有人可以帮我解决这个问题吗？

Answer 1

由于您可以沿对角线移动，因此移动次数仅受最长维度的限制，x 或y。想一想:如果下一个节点距离 +10x 和 -5y，那么它正好需要 10 步，因为你只能移动 1 x一次，y的差异由克服x差异的过程中的对角线移动弥补。

你的代码清楚地表达了这个细节:

if 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 指出的那样，每对连续点之间的最短路径保证是整个点集的最短路径，因此您会得到正确的总体答案。