Print shortest path to print a string on screen

Given screen containing aplhabets from A-Z and input string, by using remote we can go from one character to another character, remote contains only left, right, top and bottom keys. write a function that will find the shortest path to type all the charcters of given string using remote.

Example

Screen

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

INPUT
s = "CUP"

OUTPUT
Move Right
Move Right
Press OK
Move Left
Move Left
Move Down
Move Down
Move Down
Move Down
Press OK
Move Up
Press OK

In this method the main idea is to store the charcters in the screen as a 2D matrix, consider all characters in matrix one by one and find the shortest path between current character and next character in the matrix

Algorithm

1. Keep track of position of current charcter cordinates(ie, currX, currY) and also next character in sstring cordinates(ie, nextX, nextY)

2. If row difference is negative, then we move up

3. If row difference is positive, then we move down

4. If column difference is negative, then move left

5. If column difference is positive, then move right

C++ Program

#include <iostream>
using namespace std;
 
// This function takes the string and prints the shortest path
void printShortestPath(string s)
{
    int i = 0;
    // start from charcater 'A' present at position (0, 0)
    int currX = 0, currY = 0;
    while (i < s.length())
    {
        // find cordinates of next character
        int nextX = (s[i] - 'A') / 5;
        int nextY = (s[i] - 'B' + 1) % 5;
 
        // Move Up if next charcater is above
        while (currX > nextX)
        {
            cout << "Move Up" << endl;
            currX--;
        }
 
        // Move Left if next character is to the left
        while (currY > nextY)
        {
            cout << "Move Left" << endl;
            currY--;
        }
 
        // Move down if next character is below
        while (currX < nextX)
        {
            cout << "Move Down" << endl;
            currX++;
        }
 
        // Move Right if next character is to the right
        while (currY < nextY)
        {
            cout << "Move Right" << endl;
            currY++;
        }
 
        // At this point, next character is reached
        cout << "Press OK" << endl;
        i++;
    }
}
 

int main()
{
    string s = "CUP";
 
    printShortestPath(s);
 
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top