Dada una pantalla que contiene alfabetos de la A a la Z, podemos pasar de un carácter a otro utilizando un control remoto. El control remoto contiene teclas izquierda, derecha, superior e inferior.
Encuentre la ruta más corta posible para escribir todos los caracteres de la string dada usando el control remoto. La posición inicial es la parte superior izquierda y todos los caracteres de la string de entrada deben imprimirse en orden.
Pantalla:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ejemplo:
Input: “GEEK” Output: Move Down Move Right Press OK Move Up Move Right Move Right Move Right Press OK Press OK Move Left Move Left Move Left Move Left Move Down Move Down Press OK
La idea es considerar la pantalla como una array 2D de personajes. Luego, consideramos todos los caracteres de la string dada uno por uno e imprimimos la ruta más corta entre el carácter actual y el siguiente carácter en la array. Para encontrar el camino más corto, consideramos las coordenadas del carácter actual y el siguiente carácter en la array. Según la diferencia entre los valores x e y de las coordenadas del carácter actual y siguiente, nos movemos hacia la izquierda, derecha, arriba o abajo. es decir
If row difference is negative, we move up If row difference is positive, we move down If column difference is negative, we go left If column difference is positive, we go right
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print shortest possible path to
// type all characters of given string using a remote
#include <iostream>
using namespace std;
// Function to print shortest possible path to
// type all characters of given string using a remote
void printPath(string str)
{
int i = 0;
// start from character 'A' present at position (0, 0)
int curX = 0, curY = 0;
while (i < str.length())
{
// find coordinates of next character
int nextX = (str[i] - 'A') / 5;
int nextY = (str[i] - 'B' + 1) % 5;
// Move Up if destination is above
while (curX > nextX)
{
cout << "Move Up" << endl;
curX--;
}
// Move Left if destination is to the left
while (curY > nextY)
{
cout << "Move Left" << endl;
curY--;
}
// Move down if destination is below
while (curX < nextX)
{
cout << "Move Down" << endl;
curX++;
}
// Move Right if destination is to the right
while (curY < nextY)
{
cout << "Move Right" << endl;
curY++;
}
// At this point, destination is reached
cout << "Press OK" << endl;
i++;
}
}
// Driver code
int main()
{
string str = "COZY";
printPath(str);
return 0;
}
Java
// Java program to print shortest possible path to
// type all characters of given string using a remote
class GFG
{
// Function to print shortest possible path to
// type all characters of given string using a remote
static void printPath(String str)
{
int i = 0;
// start from character 'A' present at position (0, 0)
int curX = 0, curY = 0;
while (i < str.length())
{
// find coordinates of next character
int nextX = (str.charAt(i) - 'A') / 5;
int nextY = (str.charAt(i) - 'B' + 1) % 5;
// Move Up if destination is above
while (curX > nextX)
{
System.out.println("Move Up");
curX--;
}
// Move Left if destination is to the left
while (curY > nextY)
{
System.out.println("Move Left");
curY--;
}
// Move down if destination is below
while (curX < nextX)
{
System.out.println("Move Down");
curX++;
}
// Move Right if destination is to the right
while (curY < nextY)
{
System.out.println("Move Right");
curY++;
}
// At this point, destination is reached
System.out.println("Press OK");
i++;
}
}
// driver program
public static void main (String[] args)
{
String str = "COZY";
printPath(str);
}
}
// Contributed by Pramod Kumar
Python3
# Python 3 program to print shortest possible
# path to type all characters of given string
# using a remote
# Function to print shortest possible path
# to type all characters of given string
# using a remote
def printPath(str):
i = 0
# start from character 'A' present
# at position (0, 0)
curX = 0
curY = 0
while (i < len(str)):
# find coordinates of next character
nextX = int((ord(str[i]) - ord('A')) / 5)
nextY = (ord(str[i]) - ord('B') + 1) % 5
# Move Up if destination is above
while (curX > nextX):
print("Move Up")
curX -= 1
# Move Left if destination is to the left
while (curY > nextY):
print("Move Left")
curY -= 1
# Move down if destination is below
while (curX < nextX):
print("Move Down")
curX += 1
# Move Right if destination is to the right
while (curY < nextY):
print("Move Right")
curY += 1
# At this point, destination is reached
print("Press OK")
i += 1
# Driver code
if __name__ == '__main__':
str = "COZY"
printPath(str)
# This code is contributed by
# Sanjit_Prasad
C#
// C# program to print shortest
// possible path to type all
// characters of given string
// using a remote
using System;
class GFG {
// Function to print shortest
// possible path to type all
// characters of given string
// using a remote
static void printPath(String str)
{
int i = 0;
// start from character 'A'
// present at position (0, 0)
int curX = 0, curY = 0;
while (i < str.Length)
{
// find coordinates of
// next character
int nextX = (str[i] - 'A') / 5;
int nextY = (str[i] - 'B' + 1) % 5;
// Move Up if destination
// is above
while (curX > nextX)
{
Console.WriteLine("Move Up");
curX--;
}
// Move Left if destination
// is to the left
while (curY > nextY)
{
Console.WriteLine("Move Left");
curY--;
}
// Move down if destination
// is below
while (curX < nextX)
{
Console.WriteLine("Move Down");
curX++;
}
// Move Right if destination
// is to the right
while (curY < nextY)
{
Console.WriteLine("Move Right");
curY++;
}
// At this point, destination
// is reached
Console.WriteLine("Press OK");
i++;
}
}
// Driver Code
public static void Main ()
{
String str = "COZY";
printPath(str);
}
}
// This Code is contributed by nitin mittal.
PHP
<?php
// PHP program to print shortest possible path to
// type all characters of given string using a remote
// Function to print shortest possible path to
// type all characters of given string using a remote
function printPath($str)
{
$i = 0;
// start from character 'A' present at position (0, 0)
$curX = $curY = 0;
while ($i < strlen($str))
{
// find coordinates of next character
$nextX = (int)((ord($str[$i]) - ord('A')) / 5);
$nextY = (ord($str[$i]) - ord('B') + 1) % 5;
// Move Up if destination is above
while ($curX > $nextX)
{
echo "Move Up\n";
$curX--;
}
// Move Left if destination is to the left
while ($curY > $nextY)
{
echo "Move Left\n";
$curY--;
}
// Move down if destination is below
while ($curX < $nextX)
{
echo "Move Down\n";
$curX++;
}
// Move Right if destination is to the right
while ($curY < $nextY)
{
echo "Move Right\n";
$curY++;
}
// At this point, destination is reached
echo "Press OK\n";
$i++;
}
}
// Driver code
$str = "COZY";
printPath($str);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// JavaScript program to print shortest
// possible path to type all
// characters of given string
// using a remote
// Function to print shortest
// possible path to type all
// characters of given string
// using a remote
function printPath(str)
{
let i = 0;
// start from character 'A'
// present at position (0, 0)
let curX = 0, curY = 0;
while (i < str.length)
{
// find coordinates of
// next character
let nextX = parseInt((str[i].charCodeAt() -
'A'.charCodeAt()) / 5, 10);
let nextY = (str[i].charCodeAt() -
'B'.charCodeAt() + 1) % 5;
// Move Up if destination
// is above
while (curX > nextX)
{
document.write("Move Up" + "</br>");
curX--;
}
// Move Left if destination
// is to the left
while (curY > nextY)
{
document.write("Move Left" + "</br>");
curY--;
}
// Move down if destination
// is below
while (curX < nextX)
{
document.write("Move Down" + "</br>");
curX++;
}
// Move Right if destination
// is to the right
while (curY < nextY)
{
document.write("Move Right" + "</br>");
curY++;
}
// At this point, destination
// is reached
document.write("Press OK" + "</br>");
i++;
}
}
let str = "COZY";
printPath(str);
</script>
Producción:
Move Right Move Right Press OK Move Down Move Down Move Right Move Right Press OK Move Left Move Left Move Left Move Left Move Down Move Down Move Down Press OK Move Up Move Right Move Right Move Right Move Right Press OK
Complejidad de tiempo: O(n*n), donde n representa el tamaño de la string dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA