Pasos mínimos necesarios para cubrir una secuencia de puntos en una cuadrícula infinita

Dada una cuadrícula infinita, la posición inicial de la celda (x, y) y una secuencia de otra posición de la celda que debe cubrirse en el orden dado. La tarea es encontrar el número mínimo de pasos necesarios para viajar a todas esas celdas.
Nota: El movimiento se puede realizar en cualquiera de las ocho direcciones posibles desde una celda dada, es decir, desde la celda (x, y) puede moverse a cualquiera de las siguientes ocho posiciones: (x-1, y+1), (x-1 , y), (x-1, y-1), (x, y-1), (x+1, y-1), (x+1, y), (x+1, y+1), (x, y+1) es posible.

Ejemplos:

Entrada: puntos[] = [(0, 0), (1, 1), (1, 2)]
Salida: 2
Mover de (0, 0) a (1, 1) en 1 paso (diagonal) y
luego de (1, 1) a (1, 2) en 1 paso (hacia la derecha)

Entrada: puntos[] = [{4, 6}, {1, 2}, {4, 5}, {10, 12}]
Salida: 14
Mover desde (4, 6) -> (3, 5) -> (2, 4) -> (1, 3) ->
(1, 2) -> (2, 3) -> (3, 4) ->
(4, 5) -> (5, 6) -> ( 6, 7) ->
(7, 8) -> (8, 9) -> (9, 10) -> (10, 11) -> (10, 12)

Enfoque: Dado que todos los puntos dados deben cubrirse en el orden especificado. Encuentre el número mínimo de pasos necesarios para llegar desde un punto de partida al siguiente punto, luego la suma de todos esos pasos mínimos para cubrir todos los puntos sería la respuesta. Una forma de llegar desde un punto (x1, y1) a (x2, y2) es mover abs(x2-x1) pasos en dirección horizontal y abs(y2-y1) pasos en dirección vertical, pero esta no es la forma. camino más corto para llegar (x2, y2). La mejor manera sería cubrir la máxima distancia posible en dirección diagonal y permanecer en dirección horizontal o vertical.
Si miramos de cerca, esto solo se reduce al máximo de abs(x2-x1) y abs(y2-y1) . La poligonal para todos los puntos y la suma de todas las distancias diagonales será la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to cover a sequence of points
// in minimum steps in a given order.
#include <bits/stdc++.h>
using namespace std;
 
// cell structure denoted as point
struct point {
    int x, y;
};
 
// function to give minimum steps to
// move from point p1 to p2
int shortestPath(point p1, point p2)
{
    // dx is total horizontal
    // distance to be covered
    int dx = abs(p1.x - p2.x);
 
    // dy is total vertical
    // distance to be covered
    int dy = abs(p1.y - p2.y);
 
    // required answer is
    // maximum of these two
    return max(dx, dy);
}
 
// Function to return the minimum steps
int coverPoints(point sequence[], int size)
{
    int stepCount = 0;
 
    // finding steps for each
    // consecutive point in the sequence
    for (int i = 0; i < size - 1; i++) {
        stepCount += shortestPath(sequence[i],
                                  sequence[i + 1]);
    }
 
    return stepCount;
}
 
// Driver code
int main()
{
    // arr stores sequence of points
    // that are to be visited
    point arr[] = { { 4, 6 }, { 1, 2 }, { 4, 5 }, { 10, 12 } };
 
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << coverPoints(arr, n);
}

14

Complejidad de tiempo: O(N)