Minimice el costo para llegar a una celda en Matrix usando movimientos horizontales, verticales y diagonales

Dados dos puntos P ₁ (x ₁ , y ₁ ) y P ₂ (x ₂ , y ₂ ) de una array, la tarea es encontrar el costo mínimo para llegar a P ₂ desde P ₁ cuando:

• Un movimiento horizontal o vertical en cualquier dirección cuesta 1 unidad
• Un movimiento diagonal en cualquier dirección cuesta 0 unidad.

Ejemplos:

Entrada: P ₁ = {7, 4}, P ₂ = {4, 4}
Salida: 1
Explicación: Los movimientos se dan a continuación:

Los movimientos son (7, 4) -> (6, 5) -> (5, 5) -> (4, 4). 
Como solo hay 1 movimiento vertical, el costo será 1.

Entrada: P ₁  = {1, 2}, P ₂ = {2, 2}
Salida: 1

Aproximación: Los movimientos deben ser tales que haya un mínimo movimiento horizontal o vertical. Esto se puede decidir a partir de la siguiente observación: 

Si la distancia horizontal es h = (y ₂ – y ₁ ) y la distancia vertical entre los puntos es v = (x ₂ – x ₁ ):
Si   |h – v| es uniforme, solo bastan los movimientos diagonales. 
Porque las posiciones horizontales o verticales se pueden mantener con dos movimientos diagonales opuestos como se muestra en la imagen a continuación:
 

manteniendo la posición vertical

Y cuando las distancias horizontal y vertical sean iguales, puede moverse directamente a P ₂ usando movimientos diagonales.
Pero en caso de que este valor sea impar, se requiere un movimiento vertical u horizontal para hacerlo par.

Para esto, siga los siguientes pasos:

• Encuentre la distancia vertical de P ₁ a P ₂ . Digamos que es vert .
• Encuentre la distancia horizontal de P ₁ a P ₂ . Digamos que es hori .
• Siempre habrá un camino desde el origen hasta el destino moviéndose en diagonal si |hori – vert| incluso.
• Pero si |hori – vert| es extraño, entonces se requiere 1 paso, ya sea horizontal o vertical, después de eso, solo el movimiento diagonal será suficiente.

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

// C++ algorithm for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find Minimum Cost
int minCostToExit(int x1, int y1, int x2, int y2)
{
    // Finding vertical distance
    // from destination
    int vert = abs(x2 - x1);
 
    // Finding horizontal distance
    // from destination
    int hori = abs(y1 - y2);
 
    // Finding the minimum cost
    if (abs(hori - vert) % 2 == 0)
        return 0;
    else
        return 1;
}
 
// Driver code
int main()
{
    int x1 = 7;
    int y1 = 4;
    int x2 = 4, y2 = 4;
    int cost = minCostToExit(x1, y1, x2, y2);
    cout << cost;
    return 0;
}

// Java algorithm for above approach
class GFG {
 
  // Function to find Minimum Cost
  static int minCostToExit(int x1, int y1,
                           int x2, int y2)
  {
 
    // Finding vertical distance
    // from destination
    int vert = Math.abs(x2 - x1);
 
    // Finding horizontal distance
    // from destination
    int hori = Math.abs(y1 - y2);
 
    // Finding the minimum cost
    if (Math.abs(hori - vert) % 2 == 0)
      return 0;
    else
      return 1;
  }
 
  // Driver code
  public static void main(String args[]) {
    int x1 = 7;
    int y1 = 4;
    int x2 = 4, y2 = 4;
    int cost = minCostToExit(x1, y1, x2, y2);
    System.out.println(cost);
  }
}
 
// This code is contributed by Saurabh Jaiswal

# Python algorithm for above approach
import math as Math
 
# Function to find Minimum Cost
def minCostToExit (x1, y1, x2, y2):
 
    # Finding vertical distance
    # from destination
    vert = Math.fabs(x2 - x1);
 
    # Finding horizontal distance
    # from destination
    hori = Math.fabs(y1 - y2);
 
    # Finding the minimum cost
    if (Math.fabs(hori - vert) % 2 == 0):
        return 0;
    else:
        return 1;
 
# Driver code
x1 = 7
y1 = 4
x2 = 4
y2 = 4;
cost = minCostToExit(x1, y1, x2, y2);
print(cost);
 
# This code is contributed by gfgking

// C# algorithm for above approach
using System;
class GFG {
 
  // Function to find Minimum Cost
  static int minCostToExit(int x1, int y1, int x2, int y2)
  {
    // Finding vertical distance
    // from destination
    int vert = Math.Abs(x2 - x1);
 
    // Finding horizontal distance
    // from destination
    int hori = Math.Abs(y1 - y2);
 
    // Finding the minimum cost
    if (Math.Abs(hori - vert) % 2 == 0)
      return 0;
    else
      return 1;
  }
 
  // Driver code
  public static void Main()
  {
    int x1 = 7;
    int y1 = 4;
    int x2 = 4, y2 = 4;
    int cost = minCostToExit(x1, y1, x2, y2);
    Console.Write(cost);
  }
}
 
// This code is contributed by ukasp.

<script>
 
    // JavaScript algorithm for above approach
 
    // Function to find Minimum Cost
    const minCostToExit = (x1, y1, x2, y2) => {
     
        // Finding vertical distance
        // from destination
        let vert = Math.abs(x2 - x1);
 
        // Finding horizontal distance
        // from destination
        let hori = Math.abs(y1 - y2);
 
        // Finding the minimum cost
        if (Math.abs(hori - vert) % 2 == 0)
            return 0;
        else
            return 1;
    }
 
    // Driver code
    let x1 = 7;
    let y1 = 4;
    let x2 = 4, y2 = 4;
    let cost = minCostToExit(x1, y1, x2, y2);
    document.write(cost);
 
// This code is contributed by rakeshsahni
 
</script>

1

Complejidad Temporal: O(1)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.