Verifique si la secuencia de movimientos dada es circular con una repetición infinita

Dada una string str que denota una secuencia de movimientos. La tarea es verificar si los movimientos se repiten un número infinito de veces, entonces los movimientos estarán enlazados en una trayectoria circular o no. Los movimientos pueden ser de los siguientes tipos:

• “G”: ir derecho 1 unidad;
• “L”: giro de 90 grados a la izquierda;
• “R”: giro de 90 grados a la derecha.

Ejemplos:

Entrada: str = “GGLLGG”
Salida: verdadero
Explicación: Los movimientos son: (0, 0) a (0, 2); girar 180 grados; y luego vuelve a (0, 0).
Al repetir estas instrucciones, los movimientos quedan acotados en una trayectoria circular.

Entrada: str = “GG”
Salida: falso
Explicación: Los movimientos irán infinitamente solo en dirección hacia adelante.

Entrada: str = “GL”
Salida: verdadero
Explicación: Los movimientos en repetición infinita son
de (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> ( 0, 0) -> . . .
Así delimitado en este camino circular.

Aproximación: en cualquier movimiento, uno puede mirar en cualquiera de las cuatro direcciones, «Norte», «Sur», «Este» y «Oeste». La idea es considerar inicialmente pararse en la posición (0, 0) y mirar hacia el norte . Como la instrucción se da un número infinito de veces, los movimientos conducirán a una trayectoria circular si después de algunas instrucciones regresa al punto de partida.

Esto es posible solo si después de una instrucción se cambia su dirección o se vuelve al origen.

               norte

              |

              |

 NOSOTROS

              |

              |

              S 

Para averiguar la posición y dirección del robot después de cada instrucción, sume o reste ciertos valores de su posición dependiendo de la dirección.

Así es como será la dirección y el movimiento para cada dirección: 

Siga los pasos que se mencionan a continuación.

• Almacene las direcciones en forma de vector . Dado que la posición inicial está en (0, 0) , la dirección se toma en sentido contrario a las agujas del reloj para calcular la siguiente posición. Entonces, el vector es {N, W, S, E} .
• Inicialice i a 0 para realizar un seguimiento de la rotación. Aquí, 0 representa la dirección inicial. Si es 0 al final de la ejecución y la posición no es la posición inicial, la función devolverá falso.
• Inicializa xey a 0 ya que su posición inicial es (0, 0).
• Ejecute un bucle para recorrer las instrucciones una por una.
• Compruebe si hay rotación a la derecha o a la izquierda. Incremente i en 1 para la rotación a la izquierda y en 3 para la rotación a la derecha. (3 para la derecha porque una rotación a la derecha es igual a 3 rotaciones a la izquierda y aquí las direcciones se consideran en sentido contrario a las agujas del reloj)
• Si va recto, suma los valores de x e y del vector correspondiente a la i ^-ésima dirección.
• Bucle final.
• Compruebe si los movimientos conducen de vuelta a la posición inicial o si la dirección es diferente a la dirección inicial. Si alguna de estas dos condiciones es verdadera, devuelve verdadero. De lo contrario, devuelve falso.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the movements
// are repeated infinite times then
// it will be bounded in circular path or not
void isRobotBounded(string str)
{
    vector<vector<int> > dir
        = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
    int i = 0;
    int x = 0;
    int y = 0;
 
    for (int s = 0; s < str.size(); s++) {
        if (str.at(s) == 'L') {
            i = (i + 1) % 4;
        }
        else if (str.at(s) == 'R') {
            i = (i + 3) % 4;
        }
        else {
            x = x + dir[i][0];
            y = y + dir[i][1];
        }
    }
    if (x == 0 && y == 0 || i != 0)
        cout << "true";
    else
        cout << "false";
}
 
// Driver code
int main()
{
    string str = "GGLLGG";
 
    isRobotBounded(str);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to check if the movements
  // are repeated infinite times then
  // it will be bounded in circular path or not
  static void isRobotBounded(String str)
  {
    int[][] dir
      = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
    int i = 0;
    int x = 0;
    int y = 0;
 
    for (int s = 0; s < str.length(); s++) {
      if (str.charAt(s) == 'L') {
        i = (i + 1) % 4;
      }
      else if (str.charAt(s) == 'R') {
        i = (i + 3) % 4;
      }
      else {
        x = x + dir[i][0];
        y = y + dir[i][1];
      }
    }
    if (x == 0 && y == 0 || i != 0)
      System.out.println("true");
    else
      System.out.println("false");
  }
 
  // Driver code
  public static void main (String[] args) {
    String str = "GGLLGG";
 
    isRobotBounded(str);
 
  }
}
 
 
// This code is contributed by hrithikgarg03188.

# Python code for the above approach
 
# Function to check if the movements
# are repeated infinite times then
# it will be bounded in circular path or not
def isRobotBounded(str):
    dir = [[0, 1], [-1, 0], [0, -1], [1, 0]]
    i = 0
    x = 0
    y = 0
 
    for s in range(len(str)):
        if (str[s] == 'L'):
            i = (i + 1) % 4
        elif(str[s] == 'R'):
            i = (i + 3) % 4
        else:
            x = x + dir[i][0]
            y = y + dir[i][1]
    if (x == 0 and y == 0 or i != 0):
        print("true")
    else:
        print("false")
 
# Driver code
str = "GGLLGG"
isRobotBounded(str)
 
# This code is contributed by Saurabh Jaiswal

// C# code to implement above approach
using System;
class GFG
{
 
  // Function to check if the movements
  // are repeated infinite times then
  // it will be bounded in circular path or not
  static void isRobotBounded(string str)
  {
    int [,]dir
      = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
    int i = 0;
    int x = 0;
    int y = 0;
 
    for (int s = 0; s < str.Length; s++) {
      if (str[s] == 'L') {
        i = (i + 1) % 4;
      }
      else if (str[s] == 'R') {
        i = (i + 3) % 4;
      }
      else {
        x = x + dir[i, 0];
        y = y + dir[i, 1];
      }
    }
    if (x == 0 && y == 0 || i != 0)
      Console.Write("true");
    else
      Console.Write("false");
  }
 
  // Driver code
  public static void Main()
  {
    string str = "GGLLGG";
 
    isRobotBounded(str);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
 
        // Function to check if the movements
        // are repeated infinite times then
        // it will be bounded in circular path or not
        function isRobotBounded(str)
        {
            let dir
                = [[0, 1], [-1, 0], [0, -1], [1, 0]];
            let i = 0;
            let x = 0;
            let y = 0;
 
            for (let s = 0; s < str.length; s++) {
                if (str[s] == 'L') {
                    i = (i + 1) % 4;
                }
                else if (str[s] == 'R') {
                    i = (i + 3) % 4;
                }
                else {
                    x = x + dir[i][0];
                    y = y + dir[i][1];
                }
            }
            if (x == 0 && y == 0 || i != 0)
                document.write("true")
            else
                document.write("false")
        }
 
        // Driver code
        let str = "GGLLGG";
        isRobotBounded(str);
 
         // This code is contributed by Potta Lokesh
    </script>

true

Complejidad de tiempo: O(N) donde N es la longitud de la string
Espacio auxiliar: O(1)