Programming Problem hint – Uva – 10452 [ Marcus]

সবাইকে আবার স্বাগতম । বিগত কিছু পর্বের মত, আজকে আমরা আরেকটি প্রোগ্রামিং প্রবলেম নিয়ে আলোচনা করব । আমাদের shoshikkha.com এ অনেকগুলো বিভাগের মধ্যে এটি ও একটি বিভাগ, যেখানে আমরা বিভিন্ন অনলাইন জাজ এ দেয়া  প্রবলেমগুলো কীভাবে সমাধান করব, তা নিয়ে আলোচনা করে থাকি । ” প্রোগ্রামিং প্রবলেম সমাধান” করা  একটি অসাধারণ ব্যাপার । এটি এমন কোন জিনিস নয় যেটা হয়তোবা ব্যাবহারিক কিংবা প্রাতিষ্ঠানিক  কোন কিছুর সাথে সরাসরি জড়িত, কিন্তু এটি  করলে আমাদের চিন্তার দক্ষতা, ব্যাপকতা যে পরিমাণ বৃদ্ধি পায় তাতে আমাদের দৈনন্দিন জীবনের অনেক সমস্যা সমাধানে দক্ষতা বাড়ে । পাশাপাশি, সার্বিক একাডেমিক রেজাল্টের উন্নতিতে ও এর ব্যাপক ভূমিকা আছে ।

তো আমরা আজকের আলোচনায় ফিরে যায় । আজকে আমরা কথা বলব, Uva – 10452 , Marcus , এই প্রবলেমটি নিয়ে ।

Problem link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1393&mosmsg=Submission+received+with+ID+16718404

আমাদের এই প্রবলেমটি খুবই সোজা । এখানে মূলত একটা একটা ক্যারেকটার এর গ্রিড দেয়া থাকবে । যেখানে অন্তর্ভূক্ত থাকবে [A,Z] পর্যন্ত আর থাকবে @ এবং # , যেখানে @ সবসময় শেষে আর # সবসময় প্রথম লাইনে থাকবে । আমাদের এমনভাবে একটা পথ বের করতে হবে যাতে @ থেকে শুরু করে আমরা # এই ঘরে পৌছাতে পারি , আর কীভাবে আমরা ট্রাভার্স করছি সেই ডিরেকশনটা প্রিন্ট করতে পারি । এখানে ট্রাভার্স করার শর্ত হল, আমরা শুধুমাত্র  ‘IEHOVA’ এখানে যেই বর্ণমালা গুলো আছে, একমাত্র  সেই ঘরে যেতে পারব যেখানে আমাদের এগুলো আছে, আর যাবার পথে এই স্ট্রিং এ বর্ণগুলো যেই সিকুয়েন্স এ আছে সেই সিকুয়েন্স মেইনটেইন করে আমরা ট্রাভার্স করব । আর উল্লেখ্য আমাদের প্রতি মুভমেন্ট এ আমরা কেবলমাত্র সোজা, অথবা বামে আর ডানে মুভ করতে পারব ।

আমরা কীভাবে কাজ করছি তা আমরা ২য় টেস্ট কেস দিয়ে বুঝাচ্ছি ।

তো আমাদের কাজ খুবই সোজা । আমরা শেষ লাইন থেকে শুরু করে ডানে , বামে আর উপরে চেক করতে থাকব । যাতে আমাদের দেয়া সিকুয়েন্স অনুযায়ী আমরা পথটা বের করতে পারি । আর কীভাবে ট্রাভার্স করলাম তা প্রিন্ট করে দিব ।

Algorithm :

1. Check Index  (i,j+1)  or (i, j – 1) or (i-1,j) . আর খেয়াল রাখব যাতে কোনভাবেই গারবেজ ইন্ডেক্স চলে না আসে । কারণ গারবেজ ইনডেক্স হলে আমরা ভ্যালুগুলো ঠিক মত পাব না । আর verdict এই প্রবলেম এর জন্য TLE আসতে পারে ।
2. আর কীভাবে গেলাম তা অ্যারেতে সেভ করে তা প্রিন্ট করে দিব ।

Code :

আমরা আগে নিজেরা ট্রাই করব । নিতান্ত না পারলে কোডটি দেখব ।

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    int T,t,i,j;
    int n,m;
    scanf("%d",&T);
    for(t = 1; t <= T; t++)
    {
        char matrix[10][10];
        char name[] = "IEHOVA#";
        scanf("%d %d",&n,&m);
        for(i = 0; i < n; i++)
        {
            scanf("%s",matrix[i]);
        }

        for(i = 0; i < m; i++)
        {
            if(matrix[n - 1][i] == '@')
            {
                j = i;
                break;
            }
        }
        i = n - 1;
        int petechai = 0,index = -1,arr[10];
        while(i>=0)
        {
            if (index == 6) break;
            if((j+1) <= m - 1)
            {
                if(matrix[i][j+1] == name[petechai])
                {
                    petechai++;
                    j = j + 1;
                    index++;
                    arr[index] = 'r';
                }
            }
            if((j - 1) >= 0)
            {
                if(matrix[i][j-1] == name[petechai])
                {
                    petechai++;
                    j = j - 1;
                    index++;
                    arr[index] = 'l';
                }
            }
            if((i-1) >= 0)
            {
                if(matrix[i - 1][j] == name[petechai])
                {
                    petechai++;
                    i = i - 1;
                    index++;
                    arr[index] = 'f';
                }



            }
        }
        for(i = 0; i <= 6; i++)
        {
            if(i == 6)
            {
                if(arr[i] == 'f')
                {
                    printf("forth");
                }
                if(arr[i] == 'r')
                {
                    printf("right");
                }
                if(arr[i] == 'l')
                {
                    printf("left");
                }
            }
            else
            {
                if(arr[i] == 'f')
                {
                    printf("forth ");
                }
                if(arr[i] == 'r')
                {
                    printf("right ");
                }
                if(arr[i] == 'l')
                {
                    printf("left ");
                }

            }
        }
        printf("\n");


    }
    return 0;
}

তো আজকের মত এখানেই বিদায় । ঈন শা আল্লাহ সামনে আরো অনেক সুন্দর সুন্দর প্রবলেম নিয়ে কথা হবে । ততদিন সবাই ভাল থাক আর বেশি বেশি প্রবলেম সমাধান করতে থাক ।