র্যাট ইন ए মেজ সমস্যা

এই সমস্যায়, N x N আকারের একটি মেজ দেওয়া আছে। সোর্স এবং ডেস্টিনেশন লোকেশন হলো টপ-লেফট সেল এবং বটম-রাইট সেল। কিছু সেল আন্দোলনের জন্য বৈধ এবং কিছু সেল ব্লক করা। যদি একটি চূড়া শুরু থেকে ডেস্টিনেশন পর্যন্ত পথ পায় কিনা, সেটি বের করতে হবে, সম্ভব হলে চূড়ার সঠিক পথ মার্ক করতে হবে।

মেজটি বাইনারি ম্যাট্রিক্স দিয়ে দেওয়া হয়, যেখানে ১ দিয়ে মার্ক করা হলো বৈধ পথ, অন্যথায় ০ ব্লক করা সেলের জন্য।

নোট: চূড়া শুধু দুটি ডিরেকশনে মুভ করতে পারে, либо ডানে বা নিচে।

ইনপুট এবং আউটপুট

ইনপুট: এই অ্যালগরিদম মেজকে ম্যাট্রিক্স হিসেবে নেবে। ম্যাট্রিক্সে, ভ্যালু ১ ইন্ডিকেট করে ফ্রি স্পেস এবং ০ ইন্ডিকেট করে দেওয়াল বা ব্লকড এরিয়া।  এই ডায়াগ্রামে, টপ-লেফট সার্কেল ইন্ডিকেট করে শুরুর পয়েন্ট এবং বটম-রাইট সার্কেল ইন্ডিকেট করে শেষ পয়েন্ট। আউটপুট: এটি একটি ম্যাট্রিক্স ডিসপ্লে করবে। সেই ম্যাট্রিক্স থেকে, আমরা চূড়ার পথ খুঁজে পেতে পারব ডেস্টিনেশন পয়েন্টে পৌঁছানোর জন্য। 

অ্যালগরিদম

isValid(x, y)

ইনপুট: মেজে x এবং y পয়েন্ট।

আউটপুট: True যদি (x,y) প্লেস বৈধ হয়, অন্যথায় false।

শুরু
  যদি x এবং y রেঞ্জে থাকে এবং (x,y) প্লেস ব্লকড না থাকে, তবে
    return true
  return false
শেষ

solveRatMaze(x, y)

ইনপুট- শুরুর পয়েন্ট x এবং y।

আউটপুট- চূড়ার অনুসরণ করার পথ ডেস্টিনেশনে পৌঁছানোর জন্য, অন্যথায় false।

শুরু
  যদি (x,y) বটম রাইট কর্নার হয়, তবে
    প্লেসটি ১ হিসেবে মার্ক করুন
    return true
  যদি isValidPlace(x, y) = true, তবে
    (x, y) প্লেসকে ১ হিসেবে মার্ক করুন
    যদি solveRatMaze(x+1, y) = true, তবে //ফরওয়ার্ড মুভমেন্টের জন্য
      return true
    যদি solveRatMaze(x, y+1) = true, তবে //নিচে মুভমেন্টের জন্য
      return true
    ব্যাকট্র্যাক করার সময় (x,y) কে ০ হিসেবে মার্ক করুন
    return false
  return false
শেষ

উদাহরণ

#include<iostream> #define N 5 using namespace std; int maze[N][N] = { {1, 0, 0, 0, 0}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 1} }; int sol[N][N]; //ফাইনাল সলিউশন মেজ পথ এখানে স্টোর হবে void showPath() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << sol[i][j] << " "; cout << endl; } } bool isValidPlace(int x, int y) { //ফাংশন চেক করুন প্লেস মেজের ভিতরে আছে কিনা এবং ভ্যালু ১ আছে if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) return true; return false; } bool solveRatMaze(int x, int y) { if(x == N-1 && y == N-1) { //যখন (x,y) বটম রাইট রুম sol[x][y] = 1; return true; } if(isValidPlace(x, y) == true) { //চেক করুন (x,y) বৈধ কিনা sol[x][y] = 1; //বৈধ প্লেস হলে ১ সেট করুন if (solveRatMaze(x+1, y) == true) //ডানে মুভ করে পথ খুঁজুন return true; if (solveRatMaze(x, y+1) == true) //যখন x ডিরেকশন ব্লকড, নিচের ডিরেকশনে যান return true; sol[x][y] = 0; //যদি দুটোই ব্লকড, পথ নেই return false; } return false; } bool findSolution() { if(solveRatMaze(0, 0) == false) { cout << "There is no path"; return false; } showPath(); return true; } int main() { findSolution(); }

আউটপুট

1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1