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:
- Inicialice dos variables X e Y e inicie los valores como cero . Estas variables representarán las coordenadas x e y .
- Inserta X e Y en el conjunto .
- 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 .
- Inserte las coordenadas X e Y actualizadas en el paso anterior para cada carácter del conjunto.
- Al insertar las coordenadas en el paso anterior, si se encuentran coordenadas presentes, imprima Crossed .
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA