Camino más corto en un cuadrado

Lado dado de un cuadrado n y dos puntos (x ₁ , y ₁ ) y (x ₂ , y ₂ ) en los límites del cuadrado dado. La tarea es encontrar el camino más corto a través de los lados del cuadrado entre estos dos puntos donde las coordenadas de las esquinas del cuadrado son (0, 0) , (n, 0) , (0, n) y (n, n) .

Ejemplos: 

Entrada: n = 2, x1 = 0, y1 = 0, x2 = 1, y2 = 0 
Salida: 1 

Entrada: n = 26, x1 = 21, y1 = 0, x2 = 26, y2 = 14 
Salida: 19 

Acercarse: 

• Si las coordenadas x e y de un punto son mayores que las del otro y los puntos no están en lados opuestos del cuadrado, la distancia más corta será abs(x2 – x1) + abs(y2 – y1) .
• De lo contrario, la distancia más corta será igual a min((x1 + y1 + x2 + y2), (4 * n) – (x1 + y1 + x2 + y2))

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length
// of the minimum path between
// two points on a square of given side
int minPath(int n, int x1, int y1, int x2, int y2)
{
 
    // If both of the x and y coordinates
    // of one point is greater than the other
    if ((x1 <= x2 && y1 <= y2) || (x1 >= x2 && y1 >= y2))
    {
        // If the points are not on opposite sides
        if (!(abs(y2 - y1) == n || abs(x2 - x1) == n))
            return (abs(x1 - x2) + abs(y1 - y2));
    }
    return min(x1 + x2 + y1 + y2, (4 * n) - (x1 + x2 + y1 + y2));
}
 
// Driver code
int main()
{
    // Side of the square
    int n = 4;
    int x1 = 2, y1 = 0, x2 = 3, y2 = 4;
    cout << minPath(n, x1, y1, x2, y2);
 
    return 0;
}
 
// improved by Sonal Agrawal

// Java implementation of the approach
class GFG{
 
// Function to return the length
// of the minimum path between
// two points on a square of given side
static int minPath(int n, int x1, int y1,
                          int x2, int y2)
{
     
    // If both of the x and y coordinates
    // of one point is greater than the other
    if ((x1 <= x2 && y1 <= y2) ||
        (x1 >= x2 && y1 >= y2))
    {
         
        // If the points are not on opposite sides
        if (!(Math.abs(y2 - y1) == n ||
              Math.abs(x2 - x1) == n))
            return (Math.abs(x1 - x2) +
                    Math.abs(y1 - y2));
    }
    return Math.min(x1 + x2 + y1 + y2, (4 * n) -
                   (x1 + x2 + y1 + y2));
}
 
// Driver code
public static void main(String[] args)
{
     
    // Side of the square
    int n = 4;
    int x1 = 2, y1 = 0, x2 = 3, y2 = 4;
     
    System.out.println(minPath(n, x1, y1, x2, y2));
}
}
 
// This code is contributed by sanjeev2552

# Python3 implementation of above approach
 
# Function to return the length of the
# minimum path between two points
# on a square of given side
def minPath(n, x1, y1, x2, y2):
 
    # If both of the x and y coordinates
    # of one point is greater than the other
    if (((x1 <= x2 and y1 <= y2) or
        (x1 >= x2 and y1 >= y2)) and
        not (abs(y2 - y1) == n or
             abs(x2 - x1) == n)):
        return (abs(x1 - x2) + abs(y1 - y2));
 
    return min(x1 + x2 + y1 + y2, (4 * n) -
              (x1 + x2 + y1 + y2));
 
# Driver code
 
# side of the square
n = 4; x1 = 2; y1 = 0
x2 = 3; y2 = 4
print(minPath(n, x1, y1, x2, y2))
 
# This code is contributed
# by Shashank_Sharma

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the length
// of the minimum path between
// two points on a square of given side
static int minPath(int n, int x1, int y1,
                        int x2, int y2)
{
 
    // If both of the x and y coordinates
    // of one point is greater than the other
    if ((x1 <= x2 && y1 <= y2) || (x1 >= x2 && y1 >= y2))
    {
        // If the points are not on opposite sides
        if (!(Math.Abs(y2 - y1) == n || Math.Abs(x2 - x1) == n))
            return (Math.Abs(x1 - x2) + Math.Abs(y1 - y2));
    }
    return Math.Min(x1 + x2 + y1 + y2, (4 * n) - (x1 + x2 + y1 + y2));
}
 
// Driver code
public static void Main()
{
    // Side of the square
    int n = 4;
    int x1 = 2, y1 = 0, x2 = 3, y2 = 4;
    Console.Write(minPath(n, x1, y1, x2, y2));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// Php implementation of the approach
 
// Function to return the length
// of the minimum path between
// two points on a square of given side
function minPath($n, $x1, $y1, $x2, $y2)
{
 
    // If both of the x and y coordinates
    // of one point is greater than the other
    if (($x1 <= $x2 && $y1 <= $y2) || ($x1 >= $x2 && $y1 >= $y2))
    {
        // If the points are not on opposite sides
        if (!(abs($y2 - $y1) == $n || abs($x2 - $x1) == $n))
            return (abs($x1 - $x2) + abs($y1 - $y2));
    }
    return min($x1 + $x2 + $y1 + $y2, (4 * $n) - ($x1 + $x2 + $y1 + $y2));
     
}
 
// Driver code
 
// Side of the square
$n = 4;
$x1 = 2 ;
$y1 = 0 ;
$x2 = 3 ;
$y2 = 4 ;
echo minPath($n, $x1, $y1, $x2, $y2);
     
// This code is contributed by Ryuga
?>

<script>
    // Javascript implementation of the approach
     
    // Function to return the length
    // of the minimum path between
    // two points on a square of given side
    function minPath(n, x1, y1, x2, y2)
    {
 
        // If both of the x and y coordinates
        // of one point is greater than the other
        if ((x1 <= x2 && y1 <= y2) || (x1 >= x2 && y1 >= y2))
        {
         
            // If the points are not on opposite sides
            if (!(Math.abs(y2 - y1) == n || Math.abs(x2 - x1) == n))
                return (Math.abs(x1 - x2) + Math.abs(y1 - y2));
        }
        return Math.min(x1 + x2 + y1 + y2, (4 * n) - (x1 + x2 + y1 + y2));
    }
     
    // Side of the square
    let n = 4;
    let x1 = 2, y1 = 0, x2 = 3, y2 = 4;
    document.write(minPath(n, x1, y1, x2, y2));
     
    // This code is contributed by decode2207.
</script>

7