Imprima la ruta desde el origen dado hasta el destino en un plano 2-D

Dadas las coordenadas de un punto de origen (src x , src y ) y un punto de destino (dst x , dst y ) , la tarea es determinar la ruta posible para llegar al punto de destino desde el punto de origen. Desde cualquier punto (x, y) solo hay dos tipos de movimientos válidos: (2 * x + y, y) o (x, 2 * y + x) . Si la ruta no existe, imprima -1 .
Ejemplos: 
 

Entrada: (src x , src y ) = {5, 8}, (dst x , dst y ) = {83, 21} 
Salida: (5, 8) -> (5, 21) -> (31, 21) -> (83, 21)
Entrada: (src x , src y ) = {7, 3}, (dst x , dst y ) = {19, 25} 
Salida: -1 
 

Enfoque: la idea es usar hacer dos llamadas  recursivas desde cada punto
 

  1. En la primera llamada recursiva, actualice ‘x’ por (2 * x + y) y sin cambios en la coordenada y .
  2. En la segunda llamada recursiva, actualice ‘y’ por (2 * y + x) y sin cambios en la coordenada x .

Terminamos la llamada de recurrencia si las coordenadas actuales, x o y exceden las coordenadas de destino. Almacene la ruta en la pila y, después de llegar al destino, imprima los elementos de la pila 
. A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program for printing a path from
// given source to destination
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the path
void printExistPath(stack<int> sx, stack<int> sy, int last)
{
    // Base condition
    if (sx.empty() || sy.empty()) {
        return;
    }
    int x = sx.top();
    int y = sy.top();
     
    // Pop stores elements
    sx.pop();
    sy.pop();
     
    // Recursive call for printing stack
    // In reverse order
    printExistPath(sx, sy, last);
    if (sx.size() == last - 1) {
 
        cout << "(" << x << ", " << y << ")";
    }
    else {
        cout << "(" << x << ", " << y << ") -> ";
    }
}
 
// Function to store the path into
// The stack, if path exist
bool storePath(int srcX, int srcY, int destX, int destY,
            stack<int>& sx, stack<int>& sy)
{
    // Base condition
    if (srcX > destX || srcY > destY) {
        return false;
    }
     
    // Push current elements
    sx.push(srcX);
    sy.push(srcY);
     
    // Condition to check whether reach to the
    // Destination or not
    if (srcX == destX && srcY == destY) {
        printExistPath(sx, sy, sx.size());
        return true;
    }
     
    // Increment 'x' ordinate of source by (2*x+y)
    // Keeping 'y' constant
    if (storePath((2 * srcX) + srcY, srcY, destX, destY, sx, sy)) {
        return true;
    }
     
    // Increment 'y' ordinate of source by (2*y+x)
    // Keeping 'x' constant
    if (storePath(srcX, (2 * srcY) + srcX, destX, destY, sx, sy)) {
        return true;
    }
     
    // Pop current elements form stack
    sx.pop();
    sy.pop();
     
    // If no path exists
    return false;
}
 
// Utility function to check whether path exist or not
bool isPathExist(int srcX, int srcY, int destX, int destY)
{
    // To store x co-ordinate
    stack<int> sx;
     
    // To store y co-ordinate
    stack<int> sy;
     
    return storePath(srcX, srcY, destX, destY, sx, sy);
}
 
// Function to find the path
void printPath(int srcX, int srcY, int destX, int destY)
{
    if (!isPathExist(srcX, srcY, destX, destY))
    {
        // Print -1, if path doesn't exist
        cout << "-1";
    }
}
 
// Driver code
int main()
{
    int srcX = 5, srcY = 8;
     
    int destX = 83, destY = 21;
 
    // Function call
    printPath(srcX, srcY, destX, destY);
}

Java

// Java program for printing a path from
// given source to destination
import java.util.*;
 
class GFG{
 
// Function to print the path
static void printExistPath(Stack<Integer> sx,
                Stack<Integer> sy, int last)
{
    // Base condition
    if (sx.isEmpty() || sy.isEmpty()) {
        return;
    }
    int x = sx.peek();
    int y = sy.peek();
     
    // Pop stores elements
    sx.pop();
    sy.pop();
     
    // Recursive call for printing stack
    // In reverse order
    printExistPath(sx, sy, last);
    if (sx.size() == last - 1) {
 
        System.out.print("(" + x+ ", " + y+ ")");
    }
    else {
        System.out.print("(" + x+ ", " + y+ ")->");
    }
}
 
// Function to store the path into
// The stack, if path exist
static boolean storePath(int srcX, int srcY,
                        int destX, int destY,
            Stack<Integer> sx, Stack<Integer> sy)
{
    // Base condition
    if (srcX > destX || srcY > destY) {
        return false;
    }
     
    // Push current elements
    sx.add(srcX);
    sy.add(srcY);
     
    // Condition to check whether reach to the
    // Destination or not
    if (srcX == destX && srcY == destY) {
        printExistPath(sx, sy, sx.size());
        return true;
    }
     
    // Increment 'x' ordinate of source by (2*x+y)
    // Keeping 'y' constant
    if (storePath((2 * srcX) + srcY, srcY,
                    destX, destY, sx, sy))
    {
        return true;
    }
     
    // Increment 'y' ordinate of source by (2*y+x)
    // Keeping 'x' constant
    if (storePath(srcX, (2 * srcY) + srcX,
                    destX, destY, sx, sy))
    {
        return true;
    }
     
    // Pop current elements form stack
    sx.pop();
    sy.pop();
     
    // If no path exists
    return false;
}
 
// Utility function to check whether path exist or not
static boolean isPathExist(int srcX, int srcY,
                        int destX, int destY)
{
    // To store x co-ordinate
    Stack<Integer> sx = new Stack<Integer>();
     
    // To store y co-ordinate
    Stack<Integer> sy = new Stack<Integer>();
     
    return storePath(srcX, srcY, destX,
                    destY, sx, sy);
}
 
// Function to find the path
static void printPath(int srcX, int srcY,
                    int destX, int destY)
{
    if (!isPathExist(srcX, srcY, destX, destY))
    {
        // Print -1, if path doesn't exist
        System.out.print("-1");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int srcX = 5, srcY = 8;
     
    int destX = 83, destY = 21;
 
    // Function call
    printPath(srcX, srcY, destX, destY);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for printing a path from
# given source to destination
  
# Function to print the path
def printExistPath( sx,  sy, last):
 
    # Base condition
    if (len(sx) == 0 or len(sy) == 0):
        return
     
    x = sx[-1];
    y = sy[-1]
      
    # Pop stores elements
    sx.pop();
    sy.pop();
      
    # Recursive call for printing stack
    # In reverse order
    printExistPath(sx, sy, last);
     
    if (len(sx) == last - 1):
        print("(" + str(x) + ", " + str(y) + ")", end='')
 
    else:
        print("(" + str(x) + ", " + str(y) + ") -> ", end='')
         
# Function to store the path into
# The stack, if path exist
def storePath(srcX, srcY, destX, destY, sx,  sy):
 
    # Base condition
    if (srcX > destX or srcY > destY):
        return False;
      
    # Push current elements
    sx.append(srcX);
    sy.append(srcY);
      
    # Condition to check whether reach to the
    # Destination or not
    if (srcX == destX and srcY == destY):
        printExistPath(sx, sy, len(sx));
        return True;
     
    # Increment 'x' ordinate of source by (2*x+y)
    # Keeping 'y' constant
    if (storePath((2 * srcX) + srcY, srcY, destX, destY, sx, sy)):
        return True;
     
    # Increment 'y' ordinate of source by (2*y+x)
    # Keeping 'x' constant
    if (storePath(srcX, (2 * srcY) + srcX, destX, destY, sx, sy)):
        return True;
      
    # Pop current elements form stack
    sx.pop();
    sy.pop();
      
    # If no path exists
    return False;
 
# Utility function to check whether path exist or not
def isPathExist(srcX, srcY, destX, destY):
 
    # To store x co-ordinate
    sx = []
      
    # To store y co-ordinate
    sy = []
     
    return storePath(srcX, srcY, destX, destY, sx, sy);
 
# Function to find the path
def printPath(srcX, srcY, destX, destY):
 
    if (not isPathExist(srcX, srcY, destX, destY)):
     
        # Print -1, if path doesn't exist
        print("-1");
     
# Driver code
if __name__=='__main__':
     
    srcX = 5
    srcY = 8;
      
    destX = 83
    destY = 21;
  
    # Function call
    printPath(srcX, srcY, destX, destY);
 
    # This code is contributed by rutvik_56

C#

// C# program for printing a path from
// given source to destination
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to print the path
static void printExistPath(Stack<int> sx,
                Stack<int> sy, int last)
{
    // Base condition
    if (sx.Count == 0 || sy.Count == 0) {
        return;
    }
    int x = sx.Peek();
    int y = sy.Peek();
      
    // Pop stores elements
    sx.Pop();
    sy.Pop();
      
    // Recursive call for printing stack
    // In reverse order
    printExistPath(sx, sy, last);
    if (sx.Count == last - 1) {
  
        Console.Write("(" + x + ", " + y + ")");
    }
    else {
        Console.Write("(" + x + ", " + y + ")->");
    }
}
  
// Function to store the path into
// The stack, if path exist
static bool storePath(int srcX, int srcY,
                        int destX, int destY,
            Stack<int> sx, Stack<int> sy)
{
    // Base condition
    if (srcX > destX || srcY > destY) {
        return false;
    }
      
    // Push current elements
    sx.Push(srcX);
    sy.Push(srcY);
      
    // Condition to check whether reach to the
    // Destination or not
    if (srcX == destX && srcY == destY) {
        printExistPath(sx, sy, sx.Count);
        return true;
    }
      
    // Increment 'x' ordinate of source by (2*x+y)
    // Keeping 'y' constant
    if (storePath((2 * srcX) + srcY, srcY,
                    destX, destY, sx, sy))
    {
        return true;
    }
      
    // Increment 'y' ordinate of source by (2*y+x)
    // Keeping 'x' constant
    if (storePath(srcX, (2 * srcY) + srcX,
                    destX, destY, sx, sy))
    {
        return true;
    }
      
    // Pop current elements form stack
    sx.Pop();
    sy.Pop();
      
    // If no path exists
    return false;
}
  
// Utility function to check whether path exist or not
static bool isPathExist(int srcX, int srcY,
                        int destX, int destY)
{
    // To store x co-ordinate
    Stack<int> sx = new Stack<int>();
      
    // To store y co-ordinate
    Stack<int> sy = new Stack<int>();
      
    return storePath(srcX, srcY, destX,
                    destY, sx, sy);
}
  
// Function to find the path
static void printPath(int srcX, int srcY,
                    int destX, int destY)
{
    if (!isPathExist(srcX, srcY, destX, destY))
    {
        // Print -1, if path doesn't exist
        Console.Write("-1");
    }
}
  
// Driver code
public static void Main(String[] args)
{
    int srcX = 5, srcY = 8;
      
    int destX = 83, destY = 21;
  
    // Function call
    printPath(srcX, srcY, destX, destY);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
    // Javascript program for printing a path from
    // given source to destination
     
    // Function to print the path
    function printExistPath(sx, sy, last)
    {
        // Base condition
        if (sx.length == 0 || sy.length == 0) {
            return;
        }
        let x = sx[sx.length - 1];
        let y = sy[sy.length - 1];
 
        // Pop stores elements
        sx.pop();
        sy.pop();
 
        // Recursive call for printing stack
        // In reverse order
        printExistPath(sx, sy, last);
        if (x==83) {
 
            document.write("(" + x + ", " + y + ")");
        }
        else {
            document.write("(" + x + ", " + y + ") -> ");
        }
    }
 
    // Function to store the path into
    // The stack, if path exist
    function storePath(srcX, srcY, destX, destY, sx, sy)
    {
        // Base condition
        if (srcX > destX || srcY > destY) {
            return false;
        }
 
        // Push current elements
        sx.push(srcX);
        sy.push(srcY);
 
        // Condition to check whether reach to the
        // Destination or not
        if (srcX == destX && srcY == destY) {
            printExistPath(sx, sy, sx.length);
            return true;
        }
 
        // Increment 'x' ordinate of source by (2*x+y)
        // Keeping 'y' constant
        if (storePath((2 * srcX) + srcY, srcY,
                        destX, destY, sx, sy))
        {
            return true;
        }
 
        // Increment 'y' ordinate of source by (2*y+x)
        // Keeping 'x' constant
        if (storePath(srcX, (2 * srcY) + srcX,
                        destX, destY, sx, sy))
        {
            return true;
        }
 
        // Pop current elements form stack
        sx.pop();
        sy.pop();
 
        // If no path exists
        return false;
    }
 
    // Utility function to check whether path exist or not
    function isPathExist(srcX, srcY, destX, destY)
    {
        // To store x co-ordinate
        let sx = [];
 
        // To store y co-ordinate
        let sy = [];
 
        return storePath(srcX, srcY, destX, destY, sx, sy);
    }
 
    // Function to find the path
    function printPath(srcX, srcY, destX, destY)
    {
        if (!isPathExist(srcX, srcY, destX, destY))
        {
            // Print -1, if path doesn't exist
            document.write("-1");
        }
    }
     
    let srcX = 5, srcY = 8;
       
    let destX = 83, destY = 21;
   
    // Function call
    printPath(srcX, srcY, destX, destY);
 
// This code is contributed by mukesh07.
</script>
Producción: 

(5, 8) -> (5, 21) -> (31, 21) -> (83, 21)

 

Publicación traducida automáticamente

Artículo escrito por MohammadMudassir 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 *