Dada una string str y cuatro enteros X 1 , Y 1 , X 2 e Y 2 , donde (X 1 , Y 1 ) denota las coordenadas de origen y (X 2 , Y 2 ) denota las coordenadas del destino. Dada una string str , la tarea es encontrar el número mínimo de pasos de los siguientes cuatro tipos necesarios para llegar al destino desde el origen:
- Si str[i] = ‘E’: Convierta (X 1 , Y 1 ) a (X 1 + 1, Y 1 ).
- Si str[i] = ‘W’: Convierta (X 1 , Y 1 ) a (X 1 – 1, Y 1 ).
- Si str[i] = ‘N’: Convierta (X 1 , Y 1 ) a (X 1 , Y 1 + 1).
- Si str[i] = ‘S’: Convierta (X 1 , Ysub>1) a (X 1 , Y 1 – 1).
Si no se puede llegar al destino, imprima -1 .
Nota: No es necesario usar str[i] siempre y se puede omitir. Pero los caracteres omitidos se sumarán a los pasos utilizados.
Ejemplos
Entrada: str = “SESNW”, x1 = 0, y1 = 0, x2 = 1, y2 = 1
Salida: 4
Explicación:
Para pasar de (0, 0) a (1, 1) , se requiere una ‘E’ y una ‘N’ .
Por lo tanto, la ruta definida por la substring “SESN” asegura que se alcance el destino {(0, 0) -> saltar S -> E (1, 0) -> saltar S -> (1, 1)}.
Por lo tanto, la longitud mínima de la cuerda atravesada es 4.Entrada: str = “NNNNNNNN”, x1 = 1, y1 = 1, x2 = 1, y2 = 2
Salida: 1
Explicación:
Desde la posición actual (1, 1) puede moverse a la coordenada (1, 2) usando primero dirección ‘N’ .
Por lo tanto, la longitud mínima del recorrido de la cuerda es 1.
Enfoque: la idea es iterar a través de la string y realizar los movimientos hasta llegar al destino. A continuación se muestran los pasos:
- Inicialice cuatro variables pos1, pos2, pos3 y pos4 para almacenar las posiciones de E, W, N, S respectivamente.
- Ahora, verifique si (x1, y1) es igual a (x2, y2), entonces la posición actual ya es el destino, así que imprima 0 .
- De lo contrario, itere sobre la string y verifique las siguientes cuatro condiciones:
- Si x2 > x1 , itere hasta que aparezca una ‘E’ y actualice ese índice en pos1 .
- Si x2 <x1 , itere hasta que aparezca una ‘W’ y actualice ese índice en pos2 .
- Si y2 > y1 entonces itere hasta que aparezca una ‘N’ y actualice ese índice en pos3 .
- Si y2 < y1 , itere hasta que aparezca una ‘S’ y actualice ese índice en pos4 .
- Después de realizar las operaciones anteriores, compruebe si x1 != x2 e y1 != y2 y luego imprima “-1” , lo que significa que es imposible llegar al destino.
- De lo contrario, busque el máximo de pos1, pos2, pos3 y pos4 e imprímalo.
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 find the minimum length
// of string required to reach from
// source to destination
void minimum_length(int x1, int y1,
int x2, int y2,
string str)
{
// Size of the string
int n = str.size();
// Stores the index of the four
// directions E, W, N, S
int pos1, pos2, pos3, pos4;
pos1 = -1;
pos2 = -1;
pos3 = -1;
pos4 = -1;
// If destination reached
if (x1 == x2 && y1 == y2) {
cout << 0 << endl;
}
// Iterate over the string
else {
for (int i = 0; i < n; i++) {
// Move east
if (x2 > x1) {
// Change x1 according
// to direction E
if (str[i] == 'E') {
x1 = x1 + 1;
if (x1 == x2) {
pos1 = i;
}
}
}
// Move west
if (x2 < x1) {
// Change x1 according
// to direction W
if (str[i] == 'W') {
x1 = x1 - 1;
if (x1 == x2) {
pos2 = i;
}
}
}
// Move north
if (y2 > y1) {
// Change y1 according
// to direction N
if (str[i] == 'N') {
y1 = y1 + 1;
if (y1 == y2) {
pos3 = i;
}
}
}
// Move south
if (y2 < y1) {
// Change y1 according
// to direction S
if (str[i] == 'S') {
y1 = y1 - 1;
if (y1 == y2) {
pos4 = i;
}
}
}
}
int z;
// Store the max of all positions
z = max(max(max(pos1, pos2),
pos3),
pos4);
// Print the minimum length of
// string required
if (x1 == x2 && y1 == y2) {
cout << z + 1 << endl;
}
// Otherwise, it is impossible
else {
cout << "-1" << endl;
}
}
}
// Driver Code
int main()
{
// Given string
string str = "SESNW";
// Given source and destination
int x1 = 0, x2 = 1, y1 = 0, y2 = 1;
// Function Call
minimum_length(x1, y1, x2, y2, str);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Function to find the minimum length
// of string required to reach from
// source to destination
static void minimum_length(int x1, int y1,
int x2, int y2,
String str)
{
// Size of the string
int n = str.length();
// Stores the index of the four
// directions E, W, N, S
int pos1, pos2, pos3, pos4;
pos1 = -1;
pos2 = -1;
pos3 = -1;
pos4 = -1;
// If destination reached
if (x1 == x2 && y1 == y2)
{
System.out.println("0");
}
// Iterate over the string
else
{
for(int i = 0; i < n; i++)
{
// Move east
if (x2 > x1)
{
// Change x1 according
// to direction E
if (str.charAt(i) == 'E')
{
x1 = x1 + 1;
if (x1 == x2)
{
pos1 = i;
}
}
}
// Move west
if (x2 < x1)
{
// Change x1 according
// to direction W
if (str.charAt(i) == 'W')
{
x1 = x1 - 1;
if (x1 == x2)
{
pos2 = i;
}
}
}
// Move north
if (y2 > y1)
{
// Change y1 according
// to direction N
if (str.charAt(i) == 'N')
{
y1 = y1 + 1;
if (y1 == y2)
{
pos3 = i;
}
}
}
// Move south
if (y2 < y1)
{
// Change y1 according
// to direction S
if (str.charAt(i) == 'S')
{
y1 = y1 - 1;
if (y1 == y2)
{
pos4 = i;
}
}
}
}
int z;
// Store the max of all positions
z = Math.max(pos1,
Math.max(Math.max(pos2, pos3),
pos4));
// Print the minimum length of
// string required
if (x1 == x2 && y1 == y2)
{
System.out.println(z + 1);
}
// Otherwise, it is impossible
else
{
System.out.println("-1");
}
}
}
// Driver Code
public static void main (String[] args)
throws java.lang.Exception
{
// Given string
String str = "SESNW";
// Given source and destination
int x1 = 0, x2 = 1, y1 = 0, y2 = 1;
// Function call
minimum_length(x1, y1, x2, y2, str);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach
# Function to find the minimum length
# of string required to reach from
# source to destination
def minimum_length(x1, y1, x2, y2, str):
# Size of the string
n = len(str)
# Stores the index of the four
# directions E, W, N, S
pos1 = -1
pos2 = -1
pos3 = -1
pos4 = -1
# If destination reached
if (x1 == x2 and y1 == y2):
print("0")
# Iterate over the string
else:
for i in range(n):
# Move east
if (x2 > x1):
# Change x1 according
# to direction E
if (str[i] == 'E'):
x1 = x1 + 1
if (x1 == x2):
pos1 = i
# Move west
if (x2 < x1):
# Change x1 according
# to direction W
if (str[i] == 'W'):
x1 = x1 - 1
if (x1 == x2):
pos2 = i
# Move north
if (y2 > y1):
# Change y1 according
# to direction N
if (str[i] == 'N'):
y1 = y1 + 1
if (y1 == y2):
pos3 = i
# Move south
if (y2 < y1):
# Change y1 according
# to direction S
if (str[i] == 'S'):
y1 = y1 - 1
if (y1 == y2):
pos4 = i
z = 0
# Store the max of all positions
z = max(pos1, max(max(pos2, pos3), pos4))
# Print the minimum length of
# string required
if (x1 == x2 and y1 == y2):
print(z + 1)
# Otherwise, it is impossible
else:
print("-1")
# Driver Code
# Given string
str = "SESNW"
# Given source and destination
x1 = 0
x2 = 1
y1 = 0
y2 = 1
# Function call
minimum_length(x1, y1, x2, y2, str)
# This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum length
// of string required to reach from
// source to destination
static void minimum_length(int x1, int y1,
int x2, int y2,
string str)
{
// Size of the string
int n = str.Length;
// Stores the index of the four
// directions E, W, N, S
int pos1, pos2, pos3, pos4;
pos1 = -1;
pos2 = -1;
pos3 = -1;
pos4 = -1;
// If destination reached
if (x1 == x2 && y1 == y2)
{
Console.WriteLine("0");
}
// Iterate over the string
else
{
for(int i = 0; i < n; i++)
{
// Move east
if (x2 > x1)
{
// Change x1 according
// to direction E
if (str[i] == 'E')
{
x1 = x1 + 1;
if (x1 == x2)
{
pos1 = i;
}
}
}
// Move west
if (x2 < x1)
{
// Change x1 according
// to direction W
if (str[i] == 'W')
{
x1 = x1 - 1;
if (x1 == x2)
{
pos2 = i;
}
}
}
// Move north
if (y2 > y1)
{
// Change y1 according
// to direction N
if (str[i] == 'N')
{
y1 = y1 + 1;
if (y1 == y2)
{
pos3 = i;
}
}
}
// Move south
if (y2 < y1)
{
// Change y1 according
// to direction S
if (str[i] == 'S')
{
y1 = y1 - 1;
if (y1 == y2)
{
pos4 = i;
}
}
}
}
int z;
// Store the max of all positions
z = Math.Max(pos1,
Math.Max(Math.Max(pos2, pos3),
pos4));
// Print the minimum length of
// string required
if (x1 == x2 && y1 == y2)
{
Console.WriteLine(z + 1);
}
// Otherwise, it is impossible
else
{
Console.WriteLine("-1");
}
}
}
// Driver Code
public static void Main ()
{
// Given string
string str = "SESNW";
// Given source and destination
int x1 = 0, x2 = 1, y1 = 0, y2 = 1;
// Function call
minimum_length(x1, y1, x2, y2, str);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum length
// of string required to reach from
// source to destination
function minimum_length(x1, y1,
x2, y2,
str)
{
// Size of the string
var n = str.length;
// Stores the index of the four
// directions E, W, N, S
var pos1, pos2, pos3, pos4;
pos1 = -1;
pos2 = -1;
pos3 = -1;
pos4 = -1;
// If destination reached
if (x1 == x2 && y1 == y2) {
document.write(0+"<br>");
}
// Iterate over the string
else {
for (var i = 0; i < n; i++) {
// Move east
if (x2 > x1) {
// Change x1 according
// to direction E
if (str[i] == 'E') {
x1 = x1 + 1;
if (x1 == x2) {
pos1 = i;
}
}
}
// Move west
if (x2 < x1) {
// Change x1 according
// to direction W
if (str[i] == 'W') {
x1 = x1 - 1;
if (x1 == x2) {
pos2 = i;
}
}
}
// Move north
if (y2 > y1) {
// Change y1 according
// to direction N
if (str[i] == 'N')
{
y1 = y1 + 1;
if (y1 == y2)
{
pos3 = i;
}
}
}
// Move south
if (y2 < y1) {
// Change y1 according
// to direction S
if (str[i] == 'S') {
y1 = y1 - 1;
if (y1 == y2) {
pos4 = i;
}
}
}
}
var z;
// Store the max of all positions
z = Math.max(Math.max(Math.max(pos1, pos2),
pos3),
pos4);
// Print the minimum length of
// string required
if (x1 == x2 && y1 == y2) {
document.write(z + 1 + "<br>" );
}
// Otherwise, it is impossible
else {
document.write("-1<br>");;
}
}
}
// Driver Code
// Given string
var str = "SESNW";
// Given source and destination
var x1 = 0, x2 = 1, y1 = 0, y2 = 1;
// Function Call
minimum_length(x1, y1, x2, y2, str);
// This code is contributed by rrrtnx.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)