গ্রিড ট্রাভেলিং এবং ডাইনামিক প্রোগ্রামিং

আসসালামু আলাইকুম! চলে আসলাম আবারো এই সিরিজের দ্বিতীয় পর্ব নিয়ে। গত পর্ব যদি পড়ে না থাকো,তাহলে এই পর্ব শুরুর আগে অবশ্যই সেটা একবার দেখে আসা উচিত। গত পর্বের লিংক এখানে।

আচ্ছা,গত পর্বের শেষে যেমন কথা দিয়েছিলাম , সে অনুযায়ীই আজকের পর্বটা সাজানো হয়েছে। আমরা গত পর্বে দেখেছি কেবলমাত্র একটা গ্রিডে ডানে বামে নড়াচড়া করতে পারলে একটা পয়েন্ট থেকে আরেকটা পয়েন্টে কয়ভাবে যাওয়া যায়।আচ্ছা, ডানে বামের পাশাপাশি আমাদের যদি কর্ণ বরাবর যাতায়াত করার অনুমতি দেয়া হয়,তাহলে একটা পয়েন্ট থেকে আরেকটা পয়েন্টে কয়ভাবে যাওয়া যাবে,সেটা বের করতে চাইলে তোমরা কিভাবে করবে? এটার ক্ষেত্রে গণিতের কম্বিনেশনের সাহায্য নেয়া যেতে পারে,তবে তা অপেক্ষাকৃত জটিল রূপ ধারণ করতে থাকবে। মনে আছে গত পর্বের পদ্ধতি-২ এর কথা,যেখানে আমরা ডাইনামিক প্রোগ্রামিং এর সহায়তায় সমস্যাটি সমাধান করেছিলাম? আমরা আজ এই সমস্যাটিকেও একইভাবে সমাধান করবো! 😀

গত পর্বের Key Lines:

”

দেখো তো,তুমি যদি জানো যে (a,b-1) পয়েন্টে কত ভাবে আসা যায় এবং (a-1,b) পয়েন্টে কতভাবে আসা যায়,তাহলে কি তুমি বলতে পারবে না (a,b) পয়েন্টে কতভাবে আসা যায়? এটা সহজ,ওই দুইপয়েন্টে যতভাবে আসা যায়,তার যোগফলটাই হবে উত্তর! কারণ তুমি কেবলমাত্র এই দুই পয়েন্ট থেকেই (a,b) পয়েন্টে আসতে পারবে,অন্য কোনো উপায়ে পারবে না।

তাহলে আমরা যদি একটা রিকারসিভ ফাংশন লিখি এইভাবে , তাহলে আমরা যেকোনো পয়েন্ট (a,b) তে কতভাবে আসা যায় সেটি পেয়ে যাবঃ

”

আচ্ছা,এখানে থামি। আগের বার শর্ত ছিলো দুইটা,ডানে এবং বামে। এবার শর্ত হচ্ছে তিনটা। ডানে,বামে এবং কর্ণ বরাবর! তাহলে এবার বলো,একটা পয়েন্ট (a,b) তে তুমি কয়টা আলাদা আলাদা জায়গা থেকে আসতে পারো? তোমার উত্তর যদি হয় তিন,তাহলে তুমি সঠিক!
হ্যা,আমরা (a,b) পয়েন্টে (a-1,b-1) এই পয়েন্ট থেকেও এখন চাইলে আসতে পারবো! তাহলে আমাদের রিকারসিভ ফাংশনটা দেখতে যেমন হবেঃ

আর এর কোডটা আগের মতোই হবে,শুধু ফাংশনটাকে একটু পালটে দিতে হবে,এই আর কিঃ

#include <stdio.h>
#include <string.h>
long long dp[21][21];
long long solve(long long m,long long n)
{
    if(m==0 || n==0) return 1;
    if(dp[m][n]!=-1) return dp[m][n]; // agei jodi calculate kore thaki,tahole notun kore ar calculate korbona. Return kore dibo.

    else
    {
        dp[m][n] = solve(m-1,n)+ solve(m,n-1)+solve(m-1,n-1);
        return dp[m][n];
    }
}
int main()
{
    memset(dp,-1,sizeof(dp)); // puro dp array ta ke -1 diye initialize kore dilam.
    long long m,n;
    scanf("%lld%lld",&m,&n);
    printf("%lld\n",solve(m,n));

    return 0;
}

এবার আলোচনা করা যাক আরেক ধরণের সমস্যা নিয়ে। না না,একেবারে নতুন কোনো সমস্যা না,এটারই মোডিফাইড ভার্সন। মনে আছে ডিপজলের কথা? এবার আমাদের গ্রিডে ডিপজল চলে আসবে! আমাদের গ্রিডের সেই পয়েন্ট গুলোকে এভয়েড করে সামনে এগিয়ে আমাদের লক্ষ্যস্থানে পৌঁছুতে হবে! কি,পারবেনা?

এটাকে আমরা দুইভাবেই ব্যাখ্যা করবো। প্রথমে দেখাবো স্মার্ট আর শক্তিশালী ভার্সন ডাইনামিক প্রোগ্রামিং এর সাহায্যে কিভাবে এটা সমাধান করা যায়। পরের পর্বে কম্বিনেশনের পদ্ধতিটা আলোচনা করবো,কারণ ওটা অপেক্ষাকৃত জটিল! তাহলে চলো শুরু করা যাকঃ

পদ্ধতিঃ (ডাইনামিক প্রোগ্রামিং)

ধরো,তুমি (5,5) এর একটা গ্রিডের (0,0) পয়েন্টে আছো। তোমাকে (5,5) পয়েন্টে যেতে হবে। কিন্তু তুমি (2,2) পয়েন্টটা ব্যবহার করতে পারবে না,কারণ ওখানে ডিপজল আছে। গেলেই তোমাকে মেরে ফেলবে। এবার তুমি কয়ভাবে (5,5) এ যেতে পারবে?

ডাইনামিক প্রোগ্রামিং এর সাহায্যে এটা চোখের পলকেই সল্ভ করে ফেলা যায়! তুমি যেই ফাংশনটা লিখেছিলা,সেখানে শুধুমাত্র একটা শর্ত জুড়ে দাও,যাতে যেতে যেতে (2,2) পয়েন্টে আসলেই সেই পথটাকে গণনার বাইরে পাঠিয়ে দেয়া হয়! অর্থাৎ , যেই পথটা (2,2) পয়েন্ট দিয়ে যাবে,তাকে নিয়ে আমরা কোনো হিসাব করবো না,বাকিগুলো নিয়ে করবো! 😀 কিভাবে করা যায় সেটা? ফাংশনে a,b এর মান (2,2) হলেই return 0 করে দিবে,তাহলেই কাজ শেষ! ঐ পথটা হিসাবের বাইরে চলে যাবে! কোডটা দেখে আসিঃ

#include <stdio.h>
#include <string.h>
long long dp[21][21];
long long solve(long long m,long long n,long long a,long long b)
{
    if(m==0 || n==0) return 1;
    if(m==a && n==b) return 0; // ekhanei shei Dipjol er path ta avoid kora hocche.
    if(dp[m][n]!=-1) return dp[m][n]; // agei jodi calculate kore thaki,tahole notun kore ar calculate korbona. Return kore dibo.

    else
    {
        dp[m][n] = solve(m-1,n,a,b)+ solve(m,n-1,a,b);
        return dp[m][n];
    }
}
int main()
{
    memset(dp,-1,sizeof(dp)); // puro dp array ta ke -1 diye initialize kore dilam.
    long long m,n,a,b;
    scanf("%lld%lld%lld%lld",&m,&n,&a,&b);
    printf("%lld\n",solve(m,n,a,b));

    return 0;
}

চমৎকার নয় কি? এভাবে তোমরা মাল্টিপল ডিপজল এর জন্যেও সল্ভ করে ফেলতে পারবে। সেটা কিভাবে ? চিন্তা করো!

আজকের পর্ব এইটুকুই! আগামী পর্বে এই সমস্যাটার কম্বিনেশন ভার্সন এবং brilliant.org এর একটা চমৎকার গ্রিড ট্রাভেলিং এর প্রব্লেম নিয়ে হাজির হবো। সেই পর্যন্ত সবাই ভালো থাকো!