Compruebe si se puede llegar a un destino desde el origen con dos movimientos permitidos

Dadas las coordenadas de un punto de origen (x1, y1), determine si es posible llegar al punto de destino (x2, y2). Desde cualquier punto (x, y) solo existen dos tipos de movimientos válidos: 
(x, x + y) y (x + y, y). Devuelve un valor booleano verdadero si es posible; de ​​lo contrario, devuelve falso. 
Nota: Todas las coordenadas son positivas. 
Preguntado en: Expedia, Telstra
Ejemplos: 
 

Input : (x1, y1) = (2, 10)
        (x2, y2) = (26, 12)
Output : True
(2, 10)->(2, 12)->(14, 12)->(26, 12) 
is a valid path.

Input : (x1, y1) = (20, 10)
        (x2, y2) = (6, 12)
Output : False
No such path is possible because x1 > x2
and coordinates are positive

El problema se puede resolver mediante recursividad simple. El caso base sería verificar si la coordenada x o y actual es mayor que la del destino, en cuyo caso devolvemos falso. Si aún no es el punto de destino, hacemos dos llamadas para ambos movimientos válidos desde ese punto. 
Si alguno de ellos produce una ruta, devolvemos verdadero; de lo contrario, devolvemos falso. 
 

C++

// C++ program to check if a destination is reachable
// from source with two movements allowed
#include <bits/stdc++.h>
using namespace std;
 
bool isReachable(int sx, int sy, int dx, int dy)
{
    // base case
    if (sx > dx || sy > dy)
        return false;
 
    // current point is equal to destination
    if (sx == dx && sy == dy)
        return true;
 
    // check for other 2 possibilities
    return (isReachable(sx + sy, sy, dx, dy) ||
            isReachable(sx, sy + sx, dx, dy));
}
 
// Driver code
int main()
{
    int source_x = 2, source_y = 10;
    int dest_x = 26, dest_y = 12;
    if (isReachable(source_x, source_y, dest_x, dest_y))
        cout << "True\n";
    else
        cout << "False\n";
    return 0;
}

Java

// Java program to check if a destination is
// reachable from source with two movements
// allowed
 
class GFG {
     
    static boolean isReachable(int sx, int sy,
                                 int dx, int dy)
    {
         
        // base case
        if (sx > dx || sy > dy)
            return false;
     
        // current point is equal to destination
        if (sx == dx && sy == dy)
            return true;
     
        // check for other 2 possibilities
        return (isReachable(sx + sy, sy, dx, dy) ||
                isReachable(sx, sy + sx, dx, dy));
    }
     
    //driver code
    public static void main(String arg[])
    {
        int source_x = 2, source_y = 10;
        int dest_x = 26, dest_y = 12;
        if (isReachable(source_x, source_y, dest_x,
                                           dest_y))
            System.out.print("True\n");
        else
            System.out.print("False\n");
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to check if
# a destination is reachable
# from source with two movements allowed
 
def isReachable(sx, sy, dx, dy):
 
    # base case
    if (sx > dx or sy > dy):
        return False
 
    # current point is equal to destination
    if (sx == dx and sy == dy):
        return True
 
    # check for other 2 possibilities
    return (isReachable(sx + sy, sy, dx, dy) or
            isReachable(sx, sy + sx, dx, dy))
 
# Driver code
source_x, source_y = 2, 10
dest_x, dest_y = 26, 12
if (isReachable(source_x, source_y, dest_x, dest_y)):
    print("True")
else:
    print("False")
     
# This code is contributed by Anant Agarwal.

C#

// C# program to check if a destination is
// reachable from source with two movements
// allowed
using System;
 
class GFG {
     
    static bool isReachable(int sx, int sy,
                             int dx, int dy)
    {
         
        // base case
        if (sx > dx || sy > dy)
            return false;
      
        // current point is equal to destination
        if (sx == dx && sy == dy)
            return true;
      
        // check for other 2 possibilities
        return (isReachable(sx + sy, sy, dx, dy) ||
                isReachable(sx, sy + sx, dx, dy));
    }
     
    //driver code
    public static void Main()
    {
        int source_x = 2, source_y = 10;
        int dest_x = 26, dest_y = 12;
        if (isReachable(source_x, source_y, dest_x,
                                           dest_y))
            Console.Write("True\n");
        else
            Console.Write("False\n");
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to check if a
// destination is reachable
// from source with two movements
// allowed
 
function isReachable($sx, $sy, $dx, $dy)
{
     
    // base case
    if ($sx > $dx || $sy > $dy)
        return false;
 
    // current point is equal
    // to destination
    if ($sx == $dx && $sy == $dy)
        return true;
 
    // check for other 2 possibilities
    return (isReachable($sx + $sy, $sy, $dx, $dy) ||
            isReachable($sx, $sy + $sx, $dx, $dy));
}
 
    // Driver code
    $source_x = 2;
    $source_y = 10;
    $dest_x = 26;
    $dest_y = 12;
    if (isReachable($source_x, $source_y,
                       $dest_x, $dest_y))
        echo "True\n";
    else
        echo "False\n";
         
// This code is contributed by Sam007
?>

Javascript

<script>
 
// Javascript program to check if a destination is
// reachable from source with two movements
// allowed
 
    function isReachable(sx, sy, dx, dy)
    {
         
        // base case
        if (sx > dx || sy > dy)
            return false;
     
        // current point is equal to destination
        if (sx == dx && sy == dy)
            return true;
     
        // check for other 2 possibilities
        return (isReachable(sx + sy, sy, dx, dy) ||
                isReachable(sx, sy + sx, dx, dy));
    }
 
// driver program
 
        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("True\n");
        else
            document.write("False\n");
         
</script>

Producción: 
 

True

Este artículo es una contribución de Aditi Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *