সাপ এবং মই সমস্যা

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

এই সমস্যায়, গন্তব্যে পৌঁছানোর জন্য আমাদের ন্যূনতম ডাইস নিক্ষেপের সংখ্যা খুঁজে বের করতে হবে।

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

ইনপুট:সাপ এবং মইয়ের শুরু এবং শেষের অবস্থান। সাপ:26 থেকে 0, 20 থেকে 8, 16 থেকে 3, 18 থেকে 6 মই 2 থেকে 21, 4 থেকে 7, 10 থেকে 25, 19 থেকে 28 আউটপুট:ন্যূনতম ডাইস থ্রো প্রয়োজন 3

অ্যালগরিদম

minDiceThrow(সরানো, সেল)

ইনপুট: সাপ বা সিঁড়ির জন্য লাফের অবস্থান এবং মোট কক্ষের সংখ্যা।
আউটপুট: চূড়ান্ত কক্ষে পৌঁছানোর জন্য ন্যূনতম সংখ্যক ডাইস নিক্ষেপ প্রয়োজন।

প্রাথমিকভাবে সমস্ত কক্ষকে অনাদর্শিত হিসাবে চিহ্নিত করুন সংজ্ঞায়িত সারি q স্টারিং শীর্ষবিন্দুটিকে ভিজিট করা হিসাবে চিহ্নিত করুন শীর্ষবিন্দু শুরু করার জন্য শীর্ষবিন্দু সংখ্যা :=0 এবং দূরত্ব :=0 q খালি না থাকা অবস্থায় q এর মধ্যে শুরুর শীর্ষস্থান s যোগ করুন, qVert করুন :=সামনে সারির উপাদান v :=qVert এর শীর্ষবিন্দু সংখ্যা যদি v =সেল -1 হয়, তারপর //যখন এটি শেষ শীর্ষবিন্দু হয় তখন লুপ ভেঙে j :=v + 1 থেকে v + 6 এবং j <সেল থেকে একটি আইটেম মুছে ফেলুন , j 1 দ্বারা বৃদ্ধি করুন, যদি j পরিদর্শন না করা হয়, তাহলে newVert.dist :=(qVert.dist + 1) ভিজিট হিসাবে চিহ্নিত করুন যদি সাপ বা মই থাকে, তাহলে newVert.vert :=সরান[j] //জাম্প সেই অবস্থানে অন্যথায় newVert.vert :=j সারিতে newVert ঢোকান 
উদাহরণ
 
#include#include নেমস্পেস ব্যবহার করে std;struct vertex { int vert; int dist; // উৎস থেকে এই শীর্ষবিন্দুর দূরত্ব};int minDiceThrow(int move[], int cell) { bool visited[cell]; জন্য (int i =0; i  q; পরিদর্শন [0] =সত্য; //প্রাথমিকভাবে 0 শীর্ষবিন্দু s ={0, 0} থেকে শুরু হয়; q. push(গুলি); // Enqueue 0'th vertex vertex qVert; যখন (!q.empty()) { qVert =q.front(); int v =qVert.vert; if (v ==সেল-1) //যখন v গন্তব্য শীর্ষবিন্দু ব্রেক হয়; q.pop(); এর জন্য (int j=v+1; j<=(v+6) &&j 
আউটপুট
 
সর্বনিম্ন ডাইস থ্রো প্রয়োজন 3