Tempo total necessário para percorrer um caminho denotado por uma determinada string
Dado um caminho de string consistindo de caracteres 'N', 'S', 'E' e 'W' denotando o movimento de 1 unidade nas direções Norte, Sul, Leste e Oeste, respectivamente, a tarefa é encontrar o tempo necessário para viajar o completo caminho a partir da origem, se levar 2 e 1 minutos para viajar em um segmento não visitado e visitado, respectivamente.
Exemplos :
Entrada: caminho = “NNES”
Saída: 8Explicação: Como cada segmento é visitado apenas uma vez, custo = 2 * 4 = 8.
Entrada: caminho = “NSE”
Saída: 5Explicação:
Etapa 1: Viaje para o norte. Tempo decorrido = 2 minutos.
Etapa 2: viaje para o sul no mesmo segmento visitado. Tempo decorrido = 1 minuto.
Etapa 3: Viaje para o leste. Tempo decorrido = 2 minutos. Portanto, o tempo total gasto = 2 + 1 + 2 = 5.
Abordagem: A ideia é utilizar um Conjunto para armazenar todos os segmentos visitados e antes de visitar cada segmento, verifique se ele está presente ou não no Conjunto. Siga as etapas abaixo para resolver o problema.
- Inicialize um conjunto s para armazenar um par de inteiros. O conjunto armazenará todos os segmentos visitados.
- Inicialize dois inteiros x = 0 ey = 0 denotando a posição atual. Além disso, inicialize uma variável time = 0 para armazenar o tempo total necessário para percorrer o caminho completo.
- Atravesse a string e siga as etapas abaixo
- Inicialize dois inteiros p e q a x e y respectivamente.
- Se o caminho [i] é igual a 'N', incremento y , senão, se o caminho [i] é igual a 'S', decrementa y, senão , se o caminho [i] é igual a 'E', incrementa x , caso contrário, diminui x .
- Verifique se o segmento { p + x , q + y } existe ou não no conjunto . se adicionar 1 ao valor do tempo, caso contrário, adicione 2 ao valor do tempo.
- Insira o segmento { p + x , q + y } no conjunto.
- Após concluir as etapas acima, imprima o valor do tempo.
Abaixo está a implementação da abordagem acima.
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate time
// taken to travel the path
void calcTotalTime(string path)
{
// Stores total time
int time = 0;
// Initial position
int x = 0, y = 0;
// Stores visited segments
set<pair<int, int> > s;
for (int i = 0; i < path.size(); i++) {
int p = x;
int q = y;
if (path[i] == 'N')
y++;
else if (path[i] == 'S')
y--;
else if (path[i] == 'E')
x++;
else if (path[i] == 'W')
x--;
// Check whether segment
// is present in the set
if (s.find({ p + x, q + y })
== s.end()) {
// Increment the value
// of time by 2
time += 2;
// Insert segment into the set
s.insert({ p + x, q + y });
}
else
time += 1;
}
// Print the value
// of time
cout << time << endl;
}
// Driver Code
int main()
{
string path = "NSE";
calcTotalTime(path);
return 0;
}
// Java program for above approach
import java.util.*;
class GFG{
// Function to calculate time
// taken to travel the path
static void calcTotalTime(String path)
{
// Stores total time
int time = 0;
// Initial position
int x = 0, y = 0;
// Stores visited segments
Set<String> s = new HashSet<>();
for(int i = 0; i < path.length(); i++)
{
int p = x;
int q = y;
if (path.charAt(i) == 'N')
y++;
else if (path.charAt(i) == 'S')
y--;
else if (path.charAt(i) == 'E')
x++;
else if (path.charAt(i) == 'W')
x--;
// Check whether segment
// is present in the set
String o = (p + x) + " " + (q + y);
if (!s.contains(o))
{
// Increment the value
// of time by 2
time += 2;
// Insert segment into the set
s.add(o);
}
else
time += 1;
}
// Print the value
// of time
System.out.println(time);
}
// Driver Code
public static void main(String[] args)
{
String path = "NSE";
calcTotalTime(path);
}
}
// This code is contributed by Hritik
# Python 3 code for the above approach
# Function to calculate time
# taken to travel the path
def calcTotalTime(path):
# Stores total time
time = 0
# Initial position
x = 0
y = 0
# Stores visited segments
s = set([])
for i in range(len(path)):
p = x
q = y
if (path[i] == 'N'):
y += 1
elif (path[i] == 'S'):
y -= 1
elif (path[i] == 'E'):
x += 1
elif (path[i] == 'W'):
x -= 1
# Check whether segment
# is present in the set
if (p + x, q + y) not in s:
# Increment the value
# of time by 2
time += 2
# Insert segment into the set
s.add((p + x, q + y))
else:
time += 1
# Print the value
# of time
print(time)
# Driver Code
if __name__ == "__main__":
path = "NSE"
calcTotalTime(path)
# This code is contributed by ukasp.
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate time
// taken to travel the path
static void calcTotalTime(string path)
{
// Stores total time
int time = 0;
// Initial position
int x = 0, y = 0;
// Stores visited segments
HashSet<string> s = new HashSet<string>();
for(int i = 0; i < path.Length; i++)
{
int p = x;
int q = y;
if (path[i] == 'N')
y++;
else if (path[i] == 'S')
y--;
else if (path[i] == 'E')
x++;
else if (path[i] == 'W')
x--;
// Check whether segment
// is present in the set
string o = (p + x) + " " + (q + y);
if (s.Contains(o) == false)
{
// Increment the value
// of time by 2
time += 2;
// Insert segment into the set
s.Add(o);
}
else
time += 1;
}
// Print the value
// of time
Console.Write(time);
}
// Driver Code
public static void Main()
{
string path = "NSE";
calcTotalTime(path);
}
}
// This code is contributed by bgangwar59
<script>
// Javascript code for the above approach
// Function to calculate time
// taken to travel the path
function calcTotalTime(path)
{
// Stores total time
var time = 0;
// Initial position
var x = 0, y = 0;
// Stores visited segments
var s = new Set();
for(var i = 0; i < path.length; i++)
{
var p = x;
var q = y;
if (path[i] == 'N')
y++;
else if (path[i] == 'S')
y--;
else if (path[i] == 'E')
x++;
else if (path[i] == 'W')
x--;
// Check whether segment
// is present in the set
if (!s.has([p + x, q + y].toString()))
{
// Increment the value
// of time by 2
time += 2;
// Insert segment into the set
s.add([p + x, q + y].toString());
}
else
time += 1;
}
// Print the value
// of time
document.write(time)
}
// Driver Code
var path = "NSE";
calcTotalTime(path);
</script>
5
Complexidade de tempo: O (NlogN)
Espaço auxiliar: O (N)
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva