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