Origen a destino en ruta 2-D con saltos de tamaño fijo

Dado el punto de origen y el punto de destino de la ruta y dos números enteros x e y . La tarea es verificar si es posible moverse desde el origen hasta el destino con los siguientes movimientos. Si la posición actual es (a, b), entonces los movimientos válidos son: 

1. (a + x, b + y)
2. (a – x, b + y)
3. (a + x, b – y)
4. (a-x, b-y)

Ejemplos:  

Entrada: Sx = 0, Sy = 0, Dx = 0, Dy = 6, x = 2, y = 3 
Salida: Sí 
(0, 0) -> (2, 3) -> (0, 6)

Entrada: Sx = 1, Sy = 1, Dx = 3, Dy = 6, x = 1, y = 5 
Salida: No 
 

Enfoque: abordemos este problema como si los pasos fueran (a, b) -> (a + x, 0) o (a, b) -> (a – x, 0) o (a, b) -> (0) , b + y) o (a, b) -> (0, b – y). Entonces la respuesta es Sí si |Sx – Dx| módulo x = 0 y |Sy – Dy| mod y = 0 .
Es fácil ver que si la respuesta a este problema es NO, entonces la respuesta al problema original también es NO.
Volvamos al problema original y echemos un vistazo a alguna secuencia de pasos. Termina en algún punto (x _e , y _e ) . Definir cnt _x como |x _e – Sx| / x y cnt _y como |y _e– Si| / año La paridad de cnt _x es la misma que la paridad de cnt _y porque cada tipo de movimiento cambia la paridad de cnt _x y cnt _y .
Entonces la respuesta es Sí si |Sx – Dx| mod x = 0 , |Sy – Dy| módulo y = 0 y |Sx – Dx| / x módulo 2 = |Sy – Dy| / y mod 2 .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if
// it is possible to move from source
// to the destination with the given moves
bool isPossible(int Sx, int Sy, int Dx, int Dy, int x, int y)
{
    if (abs(Sx - Dx) % x == 0
        and abs(Sy - Dy) % y == 0
        and (abs(Sx - Dx) / x) % 2 == (abs(Sy - Dy) / y) % 2)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    int Sx = 0, Sy = 0, Dx = 0, Dy = 0;
    int x = 3, y = 4;
 
    if (isPossible(Sx, Sy, Dx, Dy, x, y))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java .io.*;
 
class GFG
{
     
// Function that returns true if
// it is possible to move from source
// to the destination with the given moves
static boolean isPossible(int Sx, int Sy, int Dx,
                          int Dy, int x, int y)
{
    if (Math.abs(Sx - Dx) % x == 0 &&
        Math.abs(Sy - Dy) % y == 0 &&
       (Math.abs(Sx - Dx) / x) % 2 ==
       (Math.abs(Sy - Dy) / y) % 2)
        return true;
 
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    int Sx = 0, Sy = 0, Dx = 0, Dy = 0;
    int x = 3, y = 4;
 
    if (isPossible(Sx, Sy, Dx, Dy, x, y))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by inder_verma..

# Python3 implementation of the approach
 
# Function that returns true if it is
# possible to move from source to the
# destination with the given moves
def isPossible(Sx, Sy, Dx, Dy, x, y):
    if (abs(Sx - Dx) % x == 0 and
        abs(Sy - Dy) % y == 0 and
       (abs(Sx - Dx) / x) % 2 ==
       (abs(Sy - Dy) / y) % 2):
        return True;
    return False;
 
# Driver code
Sx = 0;
Sy = 0;
Dx = 0;
Dy = 0;
x = 3;
y = 4;
 
if (isPossible(Sx, Sy, Dx, Dy, x, y)):
    print("Yes");
else:
    print("No");
 
# This code is contributed by mits

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function that returns true if
// it is possible to move from source
// to the destination with the given moves
static bool isPossible(int Sx, int Sy, int Dx,
                        int Dy, int x, int y)
{
    if (Math.Abs(Sx - Dx) % x == 0 &&
        Math.Abs(Sy - Dy) % y == 0 &&
        (Math.Abs(Sx - Dx) / x) % 2 ==
        (Math.Abs(Sy - Dy) / y) % 2)
        return true;
 
    return false;
}
 
// Driver code
static void Main()
{
    int Sx = 0, Sy = 0, Dx = 0, Dy = 0;
    int x = 3, y = 4;
 
    if (isPossible(Sx, Sy, Dx, Dy, x, y))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code is contributed by chandan_jnu

<?php
// PHP implementation of the approach
 
// Function that returns true if
// it is possible to move from source
// to the destination with the given moves
function isPossible($Sx, $Sy, $Dx,
                    $Dy, $x, $y)
{
    if (abs($Sx - $Dx) % $x == 0 &&
        abs($Sy - $Dy) % $y == 0 &&
       (abs($Sx - $Dx) / $x) % 2 ==
       (abs($Sy - $Dy) / $y) % 2)
        return true;
 
    return false;
}
 
// Driver code
$Sx = 0; $Sy = 0; $Dx = 0;
$Dy = 0; $x = 3; $y = 4;
 
if (isPossible($Sx, $Sy, $Dx,
               $Dy, $x, $y))
    echo("Yes");
else
    echo("No");
 
// This code is contributed
// by Code_Mech
?>

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if
// it is possible to move from source
// to the destination with the given moves
function isPossible(Sx, Sy, Dx, Dy, x, y)
{
    if (Math.abs(Sx - Dx) % x == 0 &&
        Math.abs(Sy - Dy) % y == 0 &&
        (Math.abs(Sx - Dx) / x) % 2 ==
        (Math.abs(Sy - Dy) / y) % 2)
        return true;
 
    return false;
}
 
// Driver code
let Sx = 0, Sy = 0, Dx = 0, Dy = 0;
let x = 3, y = 4;
 
if (isPossible(Sx, Sy, Dx, Dy, x, y))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by mukesh07
 
</script>

Yes

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)