একাধিক ধাপ বা জাম্প অনুমোদিত একটি গোলকধাঁধায় সি++ ইঁদুর

একটি n*n গ্রিড গোলকধাঁধা দেওয়া হয়েছে৷ আমাদের ইঁদুর গ্রিডের উপরের বাম কোণে উপস্থিত। এখন ইঁদুরগুলি কেবল নীচে বা সামনে যেতে পারে, এবং যদি এবং শুধুমাত্র যদি ব্লকের একটি অ-শূন্য মান থাকে এখন এই পরিবর্তনে ইঁদুরকে একাধিক লাফ দেওয়ার অনুমতি দেওয়া হয়েছে। বর্তমান সেল থেকে ইঁদুর যে সর্বোচ্চ লাফ দিতে পারে তা হল ঘরে উপস্থিত সংখ্যা, এবং এখন আপনাকে খুঁজে বের করার দায়িত্ব দেওয়া হয়েছে ইঁদুরটি গ্রিডের নীচের ডান কোণায় পৌঁছাতে পারে কিনা, উদাহরণস্বরূপ −

Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}

Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist

সমাধান খোঁজার পদ্ধতি

এই পদ্ধতিতে, আমরা ব্যাকট্র্যাকিং ব্যবহার করব প্রতিটি পথ যা ইঁদুর এখন নিতে পারে তা ট্র্যাক করতে। যদি কোনো পথ থেকে ইঁদুর আমাদের গন্তব্যে পৌঁছায়, আমরা সেই পথের জন্য সত্য ফিরে আসি এবং তারপর পথটি প্রিন্ট করি। অন্যথায়, আমরা প্রিন্ট করি যে পথটি বিদ্যমান নেই।

উদাহরণ

 
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
    int sol[N][N]){
        if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
            sol[x][y] = 1;
            return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // we include this index as a path
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take                                             //so we check for every jump in every direction
            if (solveMaze(maze, x + i, y, sol) == true) // jumping right
               return true;
            if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
               return true;
        }
        sol[x][y] = 0; // if none are true then the path doesn't exist
                   //or the path doesn't contain current cell in it
        return false;
    }
    return false;
}
int main(){
    int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 },
                   { 0, 0, 0, 1 } };
    int sol[N][N];
    memset(sol, 0, sizeof(sol));
    if(solveMaze(maze, 0, 0, sol)){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                cout << sol[i][j] << " ";
            cout << "\n";
        }
    }
    else
        cout << "Path doesn't exist\n";
    return 0;
}

আউটপুট

উপরের কোডের ব্যাখ্যা

উপরের পদ্ধতিতে, আমরা আমাদের বর্তমান সেল থেকে এটি তৈরি করতে পারে এমন প্রতিটি পথের জন্য পরীক্ষা করি এবং যখন আমরা এটি পরীক্ষা করি, তখন আমরা পাথগুলিকে এখন একটি হিসাবে চিহ্নিত করি। যখন আমাদের পথটি শেষ প্রান্তে পৌঁছে যায়, তখন আমরা পরীক্ষা করি যে সেই শেষ প্রান্তটি আমাদের গন্তব্য কিনা। এখন, যদি এটি আমাদের গন্তব্য না হয়, আমরা পিছিয়ে যাই, এবং আমরা ব্যাকট্র্যাক করার সময়, আমরা সেলটিকে 0 হিসাবে চিহ্নিত করি কারণ এই পথটি বৈধ নয়, এবং এভাবেই আমাদের কোডটি এগিয়ে যায়৷

উপসংহার

এই টিউটোরিয়ালে, আমরা একাধিক ধাপ বা জাম্পের অনুমতি সহ একটি গোলকধাঁধায় ইঁদুর সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷