C++ এ গোলকধাঁধা থেকে বেরিয়ে আসার সম্ভাবনা

এই সমস্যায়, আমাদের এন পূর্ণসংখ্যার একটি গোলকধাঁধা দেওয়া হয়েছে, প্রতিটি পূর্ণসংখ্যা নির্দেশ করে যে কতগুলি চাল করা হবে। '>' এবং '<' ব্যবহার করে নির্দেশিত দিক বরাবর। আমাদের কাজ হল গোলকধাঁধা থেকে বেরিয়ে আসা সম্ভব কিনা তা খুঁজে বের করা যদি শুরুর বিন্দুটি 0 সূচকে অবস্থান করে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক

ইনপুট −

3
2 1 1 4
> < > >

আউটপুট - হ্যাঁ

ব্যাখ্যা − শুরু থেকে সরানো, আমরা 2 অবস্থান এগিয়ে, তারপর 1 অবস্থান এগিয়ে, তারপর 4 অবস্থান এগিয়ে। এটি আমাদের গোলকধাঁধাকে সরিয়ে দেবে৷

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

আরও একটি শর্ত যা দেখা দিতে পারে তা হল একটি অসীম লুপ, অর্থাৎ এমন অবস্থা যখন ব্যবহারকারী কখনই গোলকধাঁধা থেকে বেরিয়ে আসে না, এটি হল যখন আমরা একটি পরিদর্শন অবস্থানে ফিরে আসি। সুতরাং, এই অবস্থা পরীক্ষা করার জন্য আমরা সমস্ত পরিদর্শন স্থান চিহ্নিত করব৷

উদাহরণ

আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম

#include <iostream>
using namespace std;
void isMazeSolvable (int a[], int n, string s){
   int mark[n] = {0};
   int start = 0;
   int possible = 1;
   while (start >= 0 && start < n){
      if (s == "<"){
         if (mark[start] == 0){
            mark[start] = 1;
            start -= a[start];
         } else {
            possible = 0;
            break;
         }
      } else {
         if (mark[start] == 0){
            mark[start] = 1;
            start += a[start];
         } else {
            possible = 0;
            break;
         }
      }
   }
   if (possible == 0)
      cout << "It stays inside the maze forever";
   else
      cout << "It will come out of the maze";
}
int main (){
   int n = 3;
   string s = ">><";
   int a[] = { 1, 2, 4 };
   isMazeSolvable (a, n, s);
}

আউটপুট

It will come out of the maze