একটি n*n গ্রিড মেজ (maze) দেওয়া আছে। আমাদের চূড়া (rat) গ্রिडের টপ-লেফট কর্নারে আছে। এখন চূড়াটি শুধু নিচে বা সামনে যেতে পারে, এবং শুধু তখনই যখন ব্লকে নন-জিরো (non-zero) ভ্যালু থাকে। এই ভেরিয়েশনে চূড়াটি মাল্টিপল জাম্প (multiple jumps) নিতে পারে। বর্তমান সেল থেকে চূড়া যে সর্বোচ্চ জাম্প নিতে পারে সেটি সেলে থাকা সংখ্যা দ্বারা নির্দেশিত, এবং এখন আপনার কাজ হচ্ছে চূড়া গ্রিডের বটম-রাইট কর্নারে পৌঁছাতে পারে কিনা তা বের করা। উদাহরণস্বরূপ:
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
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা ব্যাকট্র্যাকিং (backtracking) ব্যবহার করব যেন চূড়া যে সব পথ নিতে পারে সেগুলো ট্র্যাক করতে পারি। এখন যদি চূড়া যেকোনো পথ থেকে আমাদের ডেস্টিনেশন (destination) পৌঁছায়, তবে আমরা সেই পথের জন্য true রিটার্ন করব এবং তারপর পথটি প্রিন্ট করব। অন্যথায়, আমরা প্রিন্ট করব যে পথটি অস্তিত্বে নেই।
উদাহরণ
#include <bits/stdc++.h> using namespace std; #define N 4 // আমাদের গ্রিডের আকার bool solveMaze(int maze[N][N], int x, int y, // পথ খুঁজে বের করার জন্য রিকারসিভ ফাংশন int sol[N][N]){ if (x == N - 1 && y == N - 1) { // যদি আমরা গোয়াল পৌঁছাই তবে true রিটার্ন এবং গোয়ালকে ১ চিহ্নিত করুন sol[x][y] = 1; return true; } if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) { sol[x][y] = 1; // আমরা এই ইনডেক্সকে পথ হিসেবে অন্তর্ভুক্ত করি for (int i = 1; i <= maze[x][y] && i < N; i++) { // maze[x][y] নির্দেশ করে কতগুলো জাম্প নেওয়া যাবে // তাই আমরা প্রতিটি ডাইরেকশনে প্রতিটি জাম্প চেক করি if (solveMaze(maze, x + i, y, sol) == true) // ডান দিকেই জাম্প return true; if (solveMaze(maze, x, y + i, sol) == true) // নিচের দিকে জাম্প return true; } sol[x][y] = 0; // যদি কোনোটিই true না হয় তবে পথ অস্তিত্বে নেই // অথবা পথে বর্তমান সেল নেই 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; }
আউটপুট
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
উপরোক্ত কোডের ব্যাখ্যা
উপরের পদ্ধতিতে, আমরা বর্তমান সেল থেকে যে সব পথ নেওয়া সম্ভব সেগুলো চেক করি, এবং চেক করার সময় আমরা পথগুলোকে ১ দিয়ে চিহ্নিত করি। এখন যখন আমাদের পথটি ডেড-এন্ড (dead-end) এ পৌঁছায়, তবে আমরা চেক করি সেই ডেড-এন্ডটি আমাদের ডেস্টিনেশন কিনা। এখন, যদি সেটি ডেস্টিনেশন না হয়, তবে আমরা ব্যাকট্র্যাক (backtrack) করি, এবং ব্যাকট্র্যাক করার সময় আমরা সেলকে ০ দিয়ে চিহ্নিত করি কারণ এই পথটি বৈধ নয়, এবং এভাবেই আমাদের কোড এগিয়ে যায়।
উপসংহার
এই টিউটোরিয়ালে, আমরা মাল্টিপল স্টেপ বা জাম্প অনুমতিপ্রাপ্ত Rat in a Maze সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
