Cuente los puntos que se vuelven a visitar mientras sigue la ruta especificada por una string dada

Dada una string S que representa una secuencia de movimientos ( L , R , U y D ) y dos números enteros X e Y que representan las coordenadas iniciales, la tarea es encontrar el número de posiciones que se vuelven a visitar siguiendo las instrucciones especificadas en el dado. string de acuerdo con las siguientes reglas:

• Si el carácter actual es L , disminuya la coordenada x en 1 .
• Si el carácter actual es R , entonces incremente la coordenada x en 1 .
• Si el carácter actual es U , entonces incremente la coordenada y en 1 .
• Si el carácter actual es D , disminuya la coordenada y en 1 .

Ejemplos:

Entrada: S = “RDDUDL”, X = 0, Y = 0
Salida: 2
Explicación: Inicialmente la coordenada es (0, 0). El cambio de coordenadas según el orden de recorrido dado es el siguiente: 
(0, 0) -> (1, 0) -> (1, -1) -> (1, -2) -> (1, -1 ) -> (1, -2) -> (0, -2)
Por lo tanto, el número de veces que se vuelve a visitar una coordenada es 2.

Entrada: S = “RDDUDL”, X = 2, Y = 3
Salida: 2

Enfoque: Siga los pasos dados para resolver el problema:

• Inicialice un HashSet de pares que almacene el par de coordenadas visitadas mientras recorre la string dada y las coordenadas actuales en el HashSet.
• Atraviese la string S dada y realice los siguientes pasos:
  • Actualice el valor de las coordenadas {X, Y} de acuerdo con la regla dada.
  • Compruebe si la coordenada actualizada está presente en HashSet o no. Si se encuentra que es cierto , entonces incremente el conteo en 1 . De lo contrario, continúa .
• Después de completar los pasos anteriores, imprima el valor del conteo como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of times
// already visited position is revisited
// after starting traversal from {X, Y}
int count(string S, int X, int Y)
{
    int N = S.length();
 
    // Stores the x and y temporarily
    int temp_x = 0, temp_y = 0;
 
    // Stores the number of times an
    // already visited position
    // is revisited
    int count = 0;
 
    // Initialize hashset
    set<pair<int, int> > s;
 
    // Insert the starting coordinates
    s.insert({ X, Y });
 
    // Traverse over the string
    for (int i = 0; i < N; i++) {
        temp_x = X;
        temp_y = Y;
 
        // Update the coordinates according
        // to the current directions
        if (S[i] == 'U') {
            X++;
        }
        else if (S[i] == 'D') {
            X--;
        }
        else if (S[i] == 'R') {
            Y++;
        }
        else {
            Y--;
        }
 
        // If the new {X, Y} has been
        // visited before, then
        // increment the count by 1
        if (s.find({ temp_x + X, temp_y + Y })
            != s.end()) {
            count++;
        }
 
        // Otherwise
        else {
 
            // Insert new {x, y}
            s.insert({ temp_x + X,
                       temp_y + Y });
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
    string S = "RDDUDL";
    int X = 0, Y = 0;
    cout << count(S, X, Y);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG
{
 
  // Function to find the number of times
  // already visited position is revisited
  // after starting traversal from {X, Y}
  static int count(String S, int X, int Y)
  {
    int N = S.length();
 
    // Stores the x and y temporarily
    int temp_x = 0, temp_y = 0;
 
    // Stores the number of times an
    // already visited position
    // is revisited
    int count = 0;
 
    // Initialize hashset
    HashSet<String> s = new HashSet<>();
 
    // Insert the starting coordinates
    s.add((X + "#" + Y));
 
    // Traverse over the string
    for (int i = 0; i < N; i++) {
      temp_x = X;
      temp_y = Y;
 
      // Update the coordinates according
      // to the current directions
      if (S.charAt(i) == 'U') {
        X++;
      }
      else if (S.charAt(i) == 'D') {
        X--;
      }
      else if (S.charAt(i) == 'R') {
        Y++;
      }
      else {
        Y--;
      }
 
      // If the new {X, Y} has been
      // visited before, then
      // increment the count by 1
      if (s.contains((temp_x + X) + "#"
                     + (temp_y + Y))) {
        count++;
      }
 
      // Otherwise
      else {
 
        // Insert new {x, y}
        s.add((temp_x + X) + "#" + (temp_y + Y));
      }
    }
 
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    String S = "RDDUDL";
    int X = 0, Y = 0;
    System.out.print(count(S, X, Y));
  }
}
 
// This code is contributed by Kingash.

# Python3 program for the above approach
 
# Function to find the number of times
# already visited position is revisited
# after starting traversal from {X, Y}
def count(S, X, Y):
    N = len(S)
 
    # Stores the x and y temporarily
    temp_x, temp_y = 0, 0
 
    # Stores the number of times an
    # already visited position
    # is revisited
    count = 0
 
    # Initialize hashset
    s = {}
 
    # Insert the starting coordinates
    s[(X, Y)] = 1
 
    # Traverse over the string
    for i in range(N):
        temp_x = X
        temp_y = Y
 
        # Update the coordinates according
        # to the current directions
        if (S[i] == 'U'):
            X += 1
        elif (S[i] == 'D'):
            X -= 1
        elif (S[i] == 'R'):
            Y += 1
        else:
            Y -= 1
 
        # If the new {X, Y} has been
        # visited before, then
        # increment the count by 1
        if ((temp_x + X, temp_y + Y ) in s):
            count += 1
        # Otherwise
        else:
            # Insert new {x, y}
            s[(temp_x + X,temp_y + Y )] = 1
    return count
 
# Driver Code
if __name__ == '__main__':
    S = "RDDUDL"
    X,Y = 0, 0
    print (count(S, X, Y))
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
  // Function to find the number of times
  // already visited position is revisited
  // after starting traversal from {X, Y}
  static int count(String S, int X, int Y)
  {
    int N = S.Length;
 
    // Stores the x and y temporarily
    int temp_x = 0, temp_y = 0;
 
    // Stores the number of times an
    // already visited position
    // is revisited
    int count = 0;
 
    // Initialize hashset
    HashSet<String> s = new HashSet<String>();
 
    // Insert the starting coordinates
    s.Add((X + "#" + Y));
 
    // Traverse over the string
    for (int i = 0; i < N; i++) {
      temp_x = X;
      temp_y = Y;
 
      // Update the coordinates according
      // to the current directions
      if (S[i] == 'U') {
        X++;
      }
      else if (S[i] == 'D') {
        X--;
      }
      else if (S[i] == 'R') {
        Y++;
      }
      else {
        Y--;
      }
 
      // If the new {X, Y} has been
      // visited before, then
      // increment the count by 1
      if (s.Contains((temp_x + X) + "#"
                     + (temp_y + Y))) {
        count++;
      }
 
      // Otherwise
      else {
 
        // Insert new {x, y}
        s.Add((temp_x + X) + "#" + (temp_y + Y));
      }
    }
    return count;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    String S = "RDDUDL";
    int X = 0, Y = 0;
    Console.Write(count(S, X, Y));
  }
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program for the above approach
 
// Function to find the number of times
// already visited position is revisited
// after starting traversal from {X, Y}
function count(S, X, Y){
    let N = S.length;
  
    // Stores the x and y temporarily
    let temp_x = 0, temp_y = 0;
  
    // Stores the number of times an
    // already visited position
    // is revisited
    let count = 0;
  
    // Initialize hashset
    let s = new Set();
  
    // Insert the starting coordinates
    s.add((X + "#" + Y));
  
    // Traverse over the string
    for (let i = 0; i < N; i++) {
      temp_x = X;
      temp_y = Y;
  
      // Update the coordinates according
      // to the current directions
      if (S[i] == 'U') {
        X++;
      }
      else if (S[i] == 'D') {
        X--;
      }
      else if (S[i] == 'R') {
        Y++;
      }
      else {
        Y--;
      }
  
      // If the new {X, Y} has been
      // visited before, then
      // increment the count by 1
      if (s.has((temp_x + X) + "#"
                     + (temp_y + Y))) {
        count++;
      }
  
      // Otherwise
      else {
  
        // Insert new {x, y}
        s.add((temp_x + X) + "#" + (temp_y + Y));
      }
    }
  
    return count;
}
  
 
// Driver Code
 
    let S = "RDDUDL";
    let X = 0, Y = 0;
    document.write(count(S, X, Y));
   
</script>       

2

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)