Comprobar si se puede llegar a un destino desde el origen con dos movimientos permitidos | conjunto 2

Dado un par de coordenadas (X1, Y1) (origen) y (X2, Y2) (destino), la tarea es comprobar si es posible llegar al destino desde el origen mediante los siguientes movimientos desde cualquier celda (X, Y ) :

1. (X + Y, Y)
2. (X, Y + X)

Nota: Todas las coordenadas son positivas y pueden ser tan grandes como 10 ¹⁸ .

Ejemplos:

Entrada: X1 = 2, Y1 = 10, X2 = 26, Y2 = 12 
Salida: Sí

Explicación: Camino posible: (2, 10) → (2, 12) ⇾ (14, 12) → (26, 12)
Por lo tanto, existe un camino entre el origen y el destino.

Entrada: X1 = 20, Y1 = 10, X2 = 6, Y2 = 12 
Salida: No

Enfoque ingenuo: el enfoque más simple para resolver el problema es mediante el uso de la recursividad . Consulte el artículo para comprobar si se puede llegar a un destino desde el origen con dos movimientos permitidos para el enfoque recursivo.

Enfoque eficiente: la idea principal es verificar si existe o no una ruta desde las coordenadas de destino (X2, Y2) hasta la fuente (X1, Y1).

Siga los pasos a continuación para resolver el problema:

• Siga restando el menor de (X2, Y2) del mayor de (X2, Y2) y deténgase si X2 se vuelve menor que X1 o Y2 se vuelve menor que Y1 .
• Ahora, compare (X1, Y1) y modifique (X2, Y2) . Si X1 es igual a X2 e Y1 es igual a Y2 , imprima » Sí «.
• Si X1 no es igual a X2 o Y1 es igual, no Y2 , entonces imprima » No «.

Para optimizar la complejidad de la operación de resta, se puede usar la operación de módulo en su lugar. Simplemente realice x2 = x2 % y2 e y2 = y2 % x2 y verifique la condición necesaria mencionada anteriormente.

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Check if (x2, y2) can be reached
// from (x1, y1)
bool isReachable(long long x1, long long y1,
                 long long x2, long long y2)
{
    while (x2 > x1 && y2 > y1) {
 
        // Reduce x2 by y2 until it is
        // less than or equal to x1
        if (x2 > y2)
            x2 %= y2;
 
        // Reduce y2 by x2 until it is
        // less than or equal to y1
        else
            y2 %= x2;
    }
 
    // If x2 is reduced to x1
    if (x2 == x1)
 
        // Check if y2 can be
        // reduced to y1 or not
        return (y2 - y1) >= 0
               && (y2 - y1) % x1 == 0;
 
    // If y2 is reduced to y1
    else if (y2 == y1)
 
        // Check if x2 can be
        // reduced to x1 or not
        return (x2 - x1) >= 0
               && (x2 - x1) % y1 == 0;
    else
        return 0;
}
 
// Driver Code
int main()
{
    long long source_x = 2, source_y = 10;
    long long dest_x = 26, dest_y = 12;
 
    if (isReachable(source_x, source_y,
                    dest_x, dest_y))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

# Python3 program to implement
# the above approach
 
# Check if (x2, y2) can be reached
# from (x1, y1)
def isReachable(x1, y1, x2, y2):
 
    while(x2 > x1 and y2 > y1):
 
        # Reduce x2 by y2 until it is
        # less than or equal to x1
        if(x2 > y2):
            x2 %= y2
 
        # Reduce y2 by x2 until it is
        # less than or equal to y1
        else:
            y2 %= x2
 
    # If x2 is reduced to x1
    if(x2 == x1):
 
        # Check if y2 can be
        # reduced to y1 or not
        return (y2 - y1) >= 0 and (
                y2 - y1) % x1 == 0
 
    # If y2 is reduced to y1
    elif(y2 == y1):
 
        # Check if x2 can be
        # reduced to x1 or not
        return (x2 - x1) >= 0 and (
                x2 - x1) % y1 == 0
    else:
        return 0
 
# Driver Code
source_x = 2
source_y = 10
dest_x = 26
dest_y = 12
 
# Function call
if(isReachable(source_x, source_y,
                 dest_x, dest_y)):
    print("Yes")
else:
    print("No")
 
# This code is contributed by Shivam Singh

// Java program to implement
// the above approach
class GFG{
 
// Check if (x2, y2) can be reached
// from (x1, y1)
static boolean isReachable(long x1, long y1,
                           long x2, long y2)
{
    while (x2 > x1 && y2 > y1)
    {
        // Reduce x2 by y2 until it is
        // less than or equal to x1
        if (x2 > y2)
            x2 %= y2;
 
        // Reduce y2 by x2 until it is
        // less than or equal to y1
        else
            y2 %= x2;
    }
 
    // If x2 is reduced to x1
    if (x2 == x1)
 
        // Check if y2 can be
        // reduced to y1 or not
        return (y2 - y1) >= 0 &&
               (y2 - y1) % x1 == 0;
 
    // If y2 is reduced to y1
    else if (y2 == y1)
 
        // Check if x2 can be
        // reduced to x1 or not
        return (x2 - x1) >= 0 &&
               (x2 - x1) % y1 == 0;
    else
        return false;
}
 
// Driver Code
public static void main(String[] args)
{
    long source_x = 2, source_y = 10;
    long dest_x = 26, dest_y = 12;
 
    if (isReachable(source_x, source_y,
                    dest_x, dest_y))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by shikhasingrajput

// C# program to implement
// the above approach
using System;
class GFG{
 
// Check if (x2, y2) can be reached
// from (x1, y1)
static bool isReachable(long x1, long y1,
                        long x2, long y2)
{
  while (x2 > x1 &&
         y2 > y1)
  {
    // Reduce x2 by y2
    // until it is less
    // than or equal to x1
    if (x2 > y2)
      x2 %= y2;
 
    // Reduce y2 by x2
    // until it is less
    // than or equal to y1
    else
      y2 %= x2;
  }
 
  // If x2 is reduced to x1
  if (x2 == x1)
 
    // Check if y2 can be
    // reduced to y1 or not
    return (y2 - y1) >= 0 &&
           (y2 - y1) % x1 == 0;
 
  // If y2 is reduced to y1
  else if (y2 == y1)
 
    // Check if x2 can be
    // reduced to x1 or not
    return (x2 - x1) >= 0 &&
           (x2 - x1) % y1 == 0;
  else
    return false;
}
 
// Driver Code
public static void Main(String[] args)
{
  long source_x = 2, source_y = 10;
  long dest_x = 26, dest_y = 12;
 
  if (isReachable(source_x, source_y,
                  dest_x, dest_y))
    Console.Write("Yes");
  else
    Console.Write("No");
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript  program for
//the above approach
 
// Check if (x2, y2) can be reached
// from (x1, y1)
function isReachable(x1, y1, x2, y2)
{
    while (x2 > x1 && y2 > y1)
    {
        // Reduce x2 by y2 until it is
        // less than or equal to x1
        if (x2 > y2)
            x2 %= y2;
  
        // Reduce y2 by x2 until it is
        // less than or equal to y1
        else
            y2 %= x2;
    }
  
    // If x2 is reduced to x1
    if (x2 == x1)
  
        // Check if y2 can be
        // reduced to y1 or not
        return (y2 - y1) >= 0 &&
               (y2 - y1) % x1 == 0;
  
    // If y2 is reduced to y1
    else if (y2 == y1)
  
        // Check if x2 can be
        // reduced to x1 or not
        return (x2 - x1) >= 0 &&
               (x2 - x1) % y1 == 0;
    else
        return false;
}
  
// Driver Code
 
    let source_x = 2, source_y = 10;
    let dest_x = 26, dest_y = 12;
  
    if (isReachable(source_x, source_y,
                    dest_x, dest_y))
        document.write("Yes");
    else
       document.write("No");
   
</script>

Yes

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)