Min Steps in Infinite Grid

Problem: You are in an infinite 2D grid where you can move in any of the 8 directions:

(x,y) to  (x+1, y), (x - 1, y), (x, y+1), (x, y-1),

 (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1)

You are given a sequence of points and the order in 

which you need to cover the points. Give the minimum number

 of steps in which you can achieve it. You start from the first point.

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).


Solution:

As we have to cover all the given points in the specified order, if we can find the minimum number of steps required to reach from a starting point to next point, the sum of all such minimum steps for covering all the points would be our answer.

One way to reach form a point (x1,y1) to (x2, y2) is to move abs(x2-x1) steps in horizontal direction and abs(y2-y1) steps in vertical direction, but this is not the shortest path to reach (x2,y2). The best way would be to cover the maximum possible distance in diagonal direction and remaining in horizontal or vertical direction. If we look closely this just reduces to maximum of abs(x2-x1) and abs(y2-y1).

Example
x1 = 5, y1= 20
x2 = 15, y2 = 15

we first move diagonally to reach (10,15) this takes 5 steps and then we move 5 units in x direction, which again takes 5 steps. In total this is 10 steps which is equal to MAX(abs(15-5), abs(15-20))

C++ code:

int coverPoints(vector<int> &X, vector<int> &Y) {

    int s1=X.size(), s2=Y.size(),ans=0;

    for(int i=1;i<s1;i++)

    {

        ans = ans + (abs(X[i]-X[i-1])<abs(Y[i]-Y[i-1])?abs(Y[i]-Y[i-1]):abs(X[i]-X[i-1]));

    }

    return ans;

}