1266. Minimum Time Visiting All Points

On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.

You can move according to these rules:

In 1 second, you can either:
move vertically by one unit,
move horizontally by one unit, or
move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
You have to visit the points in the same order as they appear in the array.
You are allowed to pass through points that appear later in the order, but these do not count as visits.
 

Example 1:


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
Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5
 

Constraints:

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

这题让我们求出最小的时间，水平或者垂直移动一步都是1,斜着移动一步也是1,所以相对而言，最核算的方法就是斜着移动。

所以我们可以求出两个坐标相减求绝对值，这样就能知道我们水平和垂直各需要移动多少。然后同时对于该值减去较小的距离，它们的代价是1,然后再求余数部分即可。

class MinimumTimeVisitingAllPoints : public Solution {
public:
    void Exec() {

    }

    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int costs = 0;
        for (int i = 1; i < points.size(); i++) {
            int xdiff = abs(points[i - 1][0] - points[i][0]);
            int ydiff = abs(points[i - 1][1] - points[i][1]);
            int base_cost = xdiff < ydiff ? xdiff : ydiff;
            costs += base_cost;
            xdiff -= base_cost;
            ydiff -= base_cost;
            costs += abs(xdiff - ydiff);
        }
        return costs;
    }
};