Comprobar si una secuencia de ruta visita cualquier coordenada dos veces o no

Dada una string str de longitud N que solo consta de los caracteres ‘N’, ‘S’, ‘E’ o ‘W’ , cada uno representa el movimiento de una unidad al norte, sur, este u oeste , respectivamente. Un hombre comienza en el origen (0, 0) en un plano 2D y camina de acuerdo con las direcciones de la cuerda. La tarea es verificar si el hombre cruza alguna coordenada en su caminata, que ya ha visitado o no. Si se encuentra que es cierto, escriba “ Cruzado” . De lo contrario, imprima » No cruzado» .

Ejemplos:

Entrada: str = “NESW”
Salida: Cruzado
Explicación:
El camino para el hombre está dado por:
(0, 0) -> (0, 1) -> (1, 1) -> (0, 1) -> ( 0, 0).
Ya que, se vuelve a visitar la coordenada (0, 0).
Por lo tanto, imprima Cruzado como se ha cruzado en el camino.

Entrada: str = “SESS”
Salida: No cruzado
Explicación:
La ruta para el hombre está dada por:
(0, 0) -> (0, -1) -> (1, -1) -> (1, -2 ) -> (1, -3).
Desde el camino anterior, el hombre nunca volvió a visitar la misma coordenada.
Por lo tanto, imprima No cruzado.

Enfoque: La idea es mantener un conjunto para las coordenadas encontradas para verificar si las coordenadas ya visitadas ocurren o no. A continuación se muestran los pasos:

1. Inicialice dos variables X e Y e inicie los valores como cero . Estas variables representarán las coordenadas x e y .
2. Inserta X e Y en el conjunto .
3. Itere un ciclo sobre el rango [0, N) e incremente la coordenada X o Y según la siguiente condición:
   • Si el carácter es ‘N’ , incremente Y en 1 .
   • Si el carácter es ‘S’ , disminuya Y en 1 .
   • Si el carácter es ‘E’ , incremente X en 1 .
   • Si el carácter es ‘W’ , entonces disminuya X en 1 .
4. Inserte las coordenadas X e Y actualizadas en el paso anterior para cada carácter del conjunto.
5. Al insertar las coordenadas en el paso anterior, si se encuentran coordenadas presentes, imprima Crossed .
6. De lo contrario, imprima No cruzado ya que todos los puntos de coordenadas son únicos.

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 check if the man crosses
// previous visited coordinate or not
bool isCrossed(string path)
{
    if (path.size() == 0)
        return false;
 
    // Stores the count of
    // crossed vertex
    bool ans = false;
 
    // Stores (x, y) coordinates
    set<pair<int, int> > set;
 
    // The coordinates for the origin
    int x = 0, y = 0;
    set.insert({ x, y });
 
    // Iterate over the string
    for (int i = 0; i < path.size(); i++) {
 
        // Condition to increment X or
        // Y co-ordinates respectively
        if (path[i] == 'N')
            set.insert({ x, y++ });
 
        if (path[i] == 'S')
            set.insert({ x, y-- });
 
        if (path[i] == 'E')
            set.insert({ x++, y });
 
        if (path[i] == 'W')
            set.insert({ x--, y });
 
        // Check if (x, y) is already
        // visited
        if (set.find({ x, y })
            != set.end()) {
 
            ans = true;
            break;
        }
    }
 
    // Print the result
    if (ans)
        cout << "Crossed";
    else
        cout << "Not Crossed";
}
 
// Driver Code
int main()
{
    // Given string
    string path = "NESW";
 
    // Function Call
    isCrossed(path);
 
    return 0;
}

// Java program for
// the above approach
import java.awt.Point;
import java.util.HashSet;
class GFG{
 
// Function to check if the man crosses
// previous visited coordinate or not
static void isCrossed(String path)
{
  if (path.length() == 0)
    return;
 
  // Stores the count of
  // crossed vertex
  boolean ans = false;
 
  // Stores (x, y) coordinates
  HashSet<Point> set =
          new HashSet<Point>();
 
  // The coordinates for the origin
  int x = 0, y = 0;
  set.add(new Point(x, y));
 
  // Iterate over the String
  for (int i = 0; i < path.length(); i++)
  {
    // Condition to increment X or
    // Y co-ordinates respectively
    if (path.charAt(i) == 'N')
      set.add(new Point(x, y++));
 
    if (path.charAt(i) == 'S')
      set.add(new Point(x, y--));
 
    if (path.charAt(i) == 'E')
      set.add(new Point(x++, y));
 
    if (path.charAt(i) == 'W')
      set.add(new Point(x--, y));
 
    // Check if (x, y) is already
    // visited
    if (set.contains(new Point(x, y)))
    {
      ans = true;
      break;
    }
  }
 
  // Print the result
  if (ans)
    System.out.print("Crossed");
  else
    System.out.print("Not Crossed");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String
  String path = "NESW";
 
  // Function Call
  isCrossed(path);
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
 
# Function to check if the man crosses
# previous visited coordinate or not
def isCrossed(path):
 
    if (len(path) == 0):
        return bool(False)
 
    # Stores the count of
    # crossed vertex
    ans = bool(False)
 
    # Stores (x, y) coordinates
    Set = set()
 
    # The coordinates for the origin
    x, y = 0, 0
    Set.add((x, y))
 
    # Iterate over the string
    for i in range(len(path)):
 
        # Condition to increment X or
        # Y co-ordinates respectively
        if (path[i] == 'N'):
            Set.add((x, y))
            y = y + 1
 
        if (path[i] == 'S'):
            Set.add((x, y))
            y = y - 1
             
        if (path[i] == 'E'):
            Set.add((x, y))
            x = x + 1
 
        if (path[i] == 'W'):
            Set.add((x, y))
            x = x - 1
             
        # Check if (x, y) is already visited
        if (x, y) in Set:
            ans = bool(True)
            break
 
    # Print the result
    if (ans):
        print("Crossed")
    else:
        print("Not Crossed")
 
# Driver code
 
# Given string
path = "NESW"
 
# Function call
isCrossed(path)
 
# This code is contributed by divyeshrabadiya07

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if the man crosses
// previous visited coordinate or not
static void isCrossed(String path)
{
    if (path.Length == 0)
        return;
 
    // Stores the count of
    // crossed vertex
    bool ans = false;
 
    // Stores (x, y) coordinates
    HashSet<KeyValuePair<int, int>> mySet =
    new HashSet<KeyValuePair<int, int>>();
 
    // The coordinates for the origin
    int x = 0, y = 0;
    mySet.Add(new KeyValuePair<int, int>(x, y));
 
    // Iterate over the String
    for(int i = 0; i < path.Length; i++)
    {
         
        // Condition to increment X or
        // Y co-ordinates respectively
        if (path[i] == 'N')
            mySet.Add(
                new KeyValuePair<int, int>(x, y++));
 
        if (path[i] == 'S')
            mySet.Add(
                new KeyValuePair<int, int>(x, y--));
 
        if (path[i] == 'E')
            mySet.Add(
                new KeyValuePair<int, int>(x++, y));
 
        if (path[i] == 'W')
            mySet.Add(
                new KeyValuePair<int, int>(x--, y));
 
        // Check if (x, y) is already
        // visited
        if (mySet.Contains(
                new KeyValuePair<int, int>(x, y)))
        {
            ans = true;
            break;
        }
    }
 
    // Print the result
    if (ans)
        Console.Write("Crossed");
    else
        Console.Write("Not Crossed");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String
    String path = "NESW";
 
    // Function call
    isCrossed(path);
}
}
 
// This code is contributed by akhilsaini

<script>
    // Javascript program for the above approach
     
    // Function to check if the man crosses
    // previous visited coordinate or not
    function isCrossed(path)
    {
        if (path.length == 0)
            return;
 
        // Stores the count of
        // crossed vertex
        let ans = false;
 
        // Stores (x, y) coordinates
        let mySet = new Set();
 
        // The coordinates for the origin
        let x = 0, y = 0;
        mySet.add([x, y]);
 
        // Iterate over the String
        for(let i = 0; i < path.length; i++)
        {
 
            // Condition to increment X or
            // Y co-ordinates respectively
            if (path[i] == 'N')
                mySet.add([x, y++]);
 
            if (path[i] == 'S')
                mySet.add([x, y--]);
 
            if (path[i] == 'E')
                mySet.add([x++, y]);
 
            if (path[i] == 'W')
                mySet.add([x--, y]);
 
            // Check if (x, y) is already
            // visited
            if (!mySet.has([x, y]))
            {
                ans = true;
                break;
            }
        }
 
        // Print the result
        if (ans)
            document.write("Crossed");
        else
            document.write("Not Crossed");
    }
     
    // Given String
    let path = "NESW";
  
    // Function call
    isCrossed(path);
 
// This code is contributed by decode2207.
</script>

Crossed

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