সি প্রোগ্রামিং-এ স্ট্রিং প্রিন্ট করার জন্য শর্টেস্ট পাথ বের করা

একটি স্ট্রিং দেওয়া থাকলে, স্ট্রিংটি স্ক্রিনে প্রিন্ট করার জন্য শর্টেস্ট পাথ (shortest path) বের করতে হবে।

স্ক্রিনে অ্যালফাবেটগুলো নিচের ফরম্যাটে সংরক্ষিত থাকে:

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: HUP
Output: Move Down (x3) -> destination reached
        Move Left (x2) -> Move Down (x3) -> destination reached
        Move Up -> destination reached

অ্যাপ্রোচ: ক্যারেক্টারগুলো n×n ম্যাট্রিক্সে সংরক্ষিত মনে করে নিচের অপারেশন করা হয়:

• Row difference নেগেটিভ হলে: Move Up
• Row difference পজিটিভ হলে: Move Down
• Column difference নেগেটিভ হলে: Move Left
• Column difference পজিটিভ হলে: Move Right

অ্যালগরিদম

START
Step 1: Declare function void printpath(char str[])
    i=0, cx=0, cy=0
    While str[i] != '\0'
        n1 = (str[i] - 'A') / 5
        n2 = (str[i] - 'B' + 1) % 5
        While cx > n1: Print "Move Up", cx--
        While cy > n2: Print "Move Left", cy--
        While cx < n1: Print "Move Down", cx++
        While cy < n2: Print "Move Right", cy++
        Print "destination reached"
        i++
Step 2: In main()
    char str[] = "HUP"
    Call printpath(str)
STOP

সি প্রোগ্রাম

#include <stdio.h>

void printpath(char str[]) {
    int i = 0;
    int cx = 0, cy = 0;
    while (str[i] != '\0') {
        int n1 = (str[i] - 'A') / 5;
        int n2 = (str[i] - 'B' + 1) % 5;
        while (cx > n1) { printf("Move Up\n"); cx--; }
        while (cy > n2) { printf("Move Left\n"); cy--; }
        while (cx < n1) { printf("Move Down\n"); cx++; }
        while (cy < n2) { printf("Move Right\n"); cy++; }
        printf("destination reached\n");
        i++;
    }
}

int main() {
    char str[] = "HUP";
    printpath(str);
    return 0;
}

আউটপুট

Move Down
Move Down
Move Down
destination reached
Move Left
Move Left
Move Down
Move Down
Move Down
destination reached
Move Up
destination reached