Alcanzar un punto usando movimientos en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj

Posted on by Rudeus Greyrat

Dada la posición inicial y final y un número N. Dado que solo podemos movernos en cuatro direcciones, como se muestra en la imagen a continuación. Las direcciones de los movimientos son U ( \flecha arriba ), R\flecha correcta , D\flecha hacia abajo y L\flecha izquierda . Necesitamos escribir un programa para determinar si a partir de la posición inicial dada podemos llegar a la posición final dada en exactamente N movimientos en cualquier dirección (hacia la derecha o hacia la izquierda ). 
 

Ejemplos: 
 

Input: start = U , end = L , N = 3 
Output: Clockwise 
Explanation: Step 1: move clockwise to reach R
             Step 2: move clockwise to reach D
             Step 3: move clockwise to reach L 
So we reach from U to L in 3 steps moving in 
clockwise direction.

Input: start = R , end = L , N = 3
Output: Not possible 
Explanation: It is not possible to start from 
R and end at L in 3 steps moving about in any 
direction. 

Input: start = D , end = R , N = 7 
Output: Clockwise
Explanation: Starting at D, we complete one 
complete clockwise round in 4 steps to reach D 
again, then it takes 3 step to reach R

La idea para resolver este problema es observar que podemos completar una vuelta en 4 pasos viajando en cualquier dirección (hacia la derecha o hacia la izquierda), por lo que dar n%4 pasos es equivalente a dar n pasos desde el punto de partida. Por lo tanto , n se reduce a n%4 . Considere los valores de ‘U’ como 0, ‘R’ como 1, ‘D’ como 2 y ‘L’ como 3 . Si abs(value(a)-value(b)) es 2 y n también es 2, entonces podemos movernos en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj para alcanzar la posición final desde la posición inicial. Si mover k pasos en el sentido de las agujas del reloj nos lleva a la posición final desde la posición inicial, entonces podemos decir que la condición para el movimiento en el sentido de las agujas del reloj será (valor(a)+k)%4==valor(b). De manera similar, la condición para el movimiento en sentido antihorario será (valor(a)+k*3)%4==valor(b) ya que dar un paso k desde la posición a en el sentido de las agujas del reloj es equivalente a tomar (a + k*3)%4 pasos en sentido contrario a las agujas del reloj. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP program to determine if
// starting from the starting
// position we can reach the 
// end position in N moves
// moving about any direction
#include <bits/stdc++.h>
using namespace std;
 
// function that returns mark
// up value of directions
int value(char a)
{
    if (a == 'U')
        return 0;
    if (a == 'R')
        return 1;
    if (a == 'D')
        return 2;
    if (a == 'L')
        return 3;
}
 
// function to print
// the possible move
void printMove(char a, char b, int n)
{
    // mod with 4 as completing
    // 4 steps means completing
    // one single round
    n = n % 4;
 
    // when n is 2 and the
    // difference between moves is 2
    if (n == 2 and abs(value(a) -
                       value(b)) == 2)
        cout << "Clockwise or Anticlockwise";
 
    // anticlockwise condition
    else if ((value(a) + n * 3) % 4 == value(b))
        cout << "Anticlockwise";
 
    // clockwise condition
    else if ((value(a) + n) % 4 == value(b))
        cout << "Clockwise";
    else
        cout << "Not Possible";
}
 
// Driver Code
int main()
{
    char a = 'D', b = 'R';
    int n = 7;
    printMove(a, b, n);
 
    return 0;
}

Java

// Java program to determine if
// starting from the starting
// position we can reach the
// end position in N moves
// moving about any direction
class GFG
{
    // function that returns mark
    // up value of directions
    static int value(char a)
    {
        if (a == 'U')
            return 0;
        if (a == 'R')
            return 1;
        if (a == 'D')
            return 2;
        if (a == 'L')
            return 3;
             
            return -1;
    }
 
    // function to print
    // the possible move
    static void printMove(char a,
                          char b,
                          int n)
    {
        // mod with 4 as completing
        // 4 steps means completing
        // one single round
        n = n % 4;
     
        // when n is 2 and
        // the difference
        // between moves is 2
        if (n == 2 && Math.abs(value(a) -
                               value(b)) == 2)
            System.out.println("Clockwise " +
                        " or Anticlockwise");
     
        // anticlockwise condition
        else if ((value(a) + n * 3) %
                       4 == value(b))
            System.out.println("Anticlockwise");
     
        // clockwise condition
        else if ((value(a) + n) % 4 == value(b))
            System.out.println("Clockwise");
        else
            System.out.println("Not Possible");
    }
 
    // Driver Code
    public static void main(String args[])
    {
        char a = 'D', b = 'R';
        int n = 7;
        printMove(a, b, n);
    }
}
 
// This code is contributed by Sam007

Python3

# python program to determine
# if starting from the starting
# position we can reach the end
# position in N moves moving 
# any direction
 
# function that returns mark
# up value of directions
def value(a):
     
    if (a == 'U'):
        return 0
    if (a == 'R'):
        return 1
    if (a == 'D'):
        return 2
    if (a == 'L'):
        return 3
 
# function to print
# the possible move
def printMove(a, b, n):
     
    # mod with 4 as completing
    # 4 steps means completing
    # one single round
    n = n % 4;
 
    # when n is 2 and
    # the difference
    # between moves is 2
    if (n == 2 and
        abs(value(a) - value(b)) == 2):
        print ("Clockwise or Anticlockwise")
 
    # anticlockwise condition
    elif ((value(a) + n * 3) % 4 == value(b)):
        print ("Anticlockwise")
 
    # clockwise condition
    elif ((value(a) + n) % 4 == value(b)):
        print ("Clockwise")
    else:
        print ("Not Possible")
 
 
# Driver Code
a = 'D'
b = 'R'
n = 7
printMove(a, b, n)
 
# This code is contributed by Sam007.

C#

// C# program to determine
// if starting from the
// starting position we
// can reach the end position
// in N moves moving about
// any direction
using System;
 
class GFG
{
    // function that returns mark
    // up value of directions
    static int value(char a)
    {
        if (a == 'U')
            return 0;
        if (a == 'R')
            return 1;
        if (a == 'D')
            return 2;
        if (a == 'L')
            return 3;
         
            return -1;
    }
 
    // function to print
    // the possible move
    static void printMove(char a,
                          char b,
                          int n)
    {
        // mod with 4 as completing
        // 4 steps means completing
        // one single round
        n = n % 4;
     
        // when n is 2 and
        // the difference
        // between moves is 2
        if (n == 2 && Math.Abs(value(a) -
                               value(b)) == 2)
            Console.Write("Clockwise " +
                    "or Anticlockwise");
     
        // anticlockwise condition
        else if ((value(a) + n * 3) %
                        4 == value(b))
            Console.Write("Anticlockwise");
     
        // clockwise condition
        else if ((value(a) + n) %
                    4 == value(b))
            Console.WriteLine("Clockwise");
        else
            Console.WriteLine("Not Possible");
    }
 
    // Driver Code
    public static void Main()
    {
    char a = 'D', b = 'R';
    int n = 7;
    printMove(a, b, n);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to determine
// if starting from the
// starting position we can
// reach the end position in
// N moves moving about
// any direction
 
// function that returns mark
// up value of directions
 
function value($a)
{
    if ($a == 'U')
        return 0;
    if ($a == 'R')
        return 1;
    if ($a == 'D')
        return 2;
    if ($a == 'L')
        return 3;
}
 
// function to print
// the possible move
function printMove($a, $b,$n)
{
    // mod with 4 as completing
    // 4 steps means completing
    // one single round
    $n = $n % 4;
 
    // when n is 2 and the
    // difference between
    // moves is 2
    if ($n == 2 and abs(value($a) -
                        value($b)) == 2)
        echo "Clockwise or Anticlockwise";
 
    // anticlockwise condition
    else if ((value($a) + $n * 3) %
                    4 == value($b))
        echo "Anticlockwise";
 
    // clockwise condition
    else if ((value($a) + $n) %
                4 == value($b))
        echo "Clockwise";
    else
        echo "Not Possible";
}
 
// Driver Code
$a = 'D'; $b = 'R';
$n = 7;
printMove($a, $b, $n);
 
// This code is contributed ajit.
?>

Javascript

<script>
 
// JavaScript program to determine if
// starting from the starting
// position we can reach the
// end position in N moves
// moving about any direction
 
    // function that returns mark
    // up value of directions
    function value(a)
    {
        if (a == 'U')
            return 0;
        if (a == 'R')
            return 1;
        if (a == 'D')
            return 2;
        if (a == 'L')
            return 3;
               
            return -1;
    }
   
    // function to print
    // the possible move
    function printMove(a, b, n)
    {
        // mod with 4 as completing
        // 4 steps means completing
        // one single round
        n = n % 4;
       
        // when n is 2 and
        // the difference
        // between moves is 2
        if (n == 2 && Math.abs(value(a) -
                               value(b)) == 2)
            document.write("Clockwise " +
                        " or Anticlockwise");
       
        // anticlockwise condition
        else if ((value(a) + n * 3) %
                       4 == value(b))
            document.write("Anticlockwise");
       
        // clockwise condition
        else if ((value(a) + n) % 4 == value(b))
            document.write("Clockwise");
        else
            document.write("Not Possible");
    }
   
 
// Driver code
     
        let a = 'D', b = 'R';
        let n = 7;
        printMove(a, b, n);
     
    // This code is contributed by code_hunt.
</script>

Producción : 
 

Clockwise

 Complejidad de tiempo : O (1), ya que no estamos usando ningún bucle o recursión para atravesar.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

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