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