আমরা সবাই স্নেক অ্যান্ড ল্যাডার খেলা সম্পর্কে জানি। এই খেলায়, বোর্ডে কিছু রুম থাকে রুম নম্বরের সাথে। কিছু রুম ল্যাডার দিয়ে সংযুক্ত থাকে অথবা স্নেক দিয়ে। যখন আমরা একটি ল্যাডার পাই, আমরা সিকোয়েন্সিয়ালি নয়ে কিছু রুম ক্লাইম আপ করে ডেস্টিনেশনের কাছে পৌঁছাতে পারি। একইভাবে, যখন আমরা একটি স্নেক পাই, সেটি আমাদেরকে একটি নিচের রুমে পাঠিয়ে দেয় যাতে আমরা সেখান থেকে আবার যাত্রা শুরু করি।
এই সমস্যায়, আমাদের খুঁজে বের করতে হবে শুরুর পয়েন্ট থেকে ডেস্টিনেশনে পৌঁছাতে ন্যূনতম কতবার ডাইস থ্রো করতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: স্নেক এবং ল্যাডারের শুরুর এবং শেষ লোকেশন। স্নেক: ২৬ থেকে ০, ২০ থেকে ৮, ১৬ থেকে ৩, ১৮ থেকে ৬ ল্যাডার: ২ থেকে ২১, ৪ থেকে ৭, ১০ থেকে ২৫, ১৯ থেকে ২৮ আউটপুট: ন্যূনতম ডাইস থ্রো প্রয়োজন: ৩
এলগরিদম
minDiceThrow(move, cell)
ইনপুট: স্নেক বা ল্যাডারের জাম্প লোকেশন, এবং মোট সেলের সংখ্যা।
আউটপুট: ফাইনাল সেলে পৌঁছাতে ন্যূনতম ডাইস থ্রো की সংখ্যা।
শুরু
প্রাথমিকভাবে সব সেলকে অনভিজিটেড চিহ্নিত করুন
একটি কিউ q সংজ্ঞায়িত করুন
শুরুর ভার্টেক্সকে ভিজিটেড চিহ্নিত করুন
শুরুর ভার্টেক্সের জন্য ভার্টেক্স নম্বর := 0 এবং দূরত্ব := 0
শুরুর ভার্টেক্স s কে q-তে যোগ করুন
যতক্ষণ q খালি নয়, করুন
qVert := কিউর ফ্রন্ট এলিমেন্ট
v := qVert-এর ভার্টেক্স নম্বর
যদি v = cell - 1, তবে // যখন এটি লাস্ট ভার্টেক্স
লুপ ব্রেক করুন
কিউ থেকে একটি আইটেম ডিলিট করুন
j := v + 1, থেকে v + 6 এবং j < cell, j কে ১ বাড়িয়ে, করুন
যদি j ভিজিটেড না থাকে, তবে
newVert.dist := (qVert.dist + 1)
v কে ভিজিটেড চিহ্নিত করুন
যদি স্নেক বা ল্যাডার থাকে, তবে
newVert.vert := move[j] // সেই লোকেশনে জাম্প করুন
অন্যথায়
newVert.vert := j
newVert কে কিউতে ইনসার্ট করুন
শর্ত শেষ
শেষ লুপ
শেষ লুপ
return qVert.dist
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <queue>
using namespace std;
struct vertex {
int vert;
int dist; // সোর্স থেকে এই ভার্টেক্সের দূরত্ব
};
int minDiceThrow(int move[], int cell) {
bool visited[cell];
for (int i = 0; i < cell; i++)
visited[i] = false; // প্রাথমিকভাবে সব সেল অনভিজিটেড
queue<vertex> q;
visited[0] = true; // প্রাথমিকভাবে ০ থেকে শুরু
vertex s = {0, 0};
q.push(s); // ০-তম ভার্টেক্স ইনকিউ করুন
vertex qVert;
while (!q.empty()) {
qVert = q.front();
int v = qVert.vert;
if (v == cell-1) // যখন v ডেস্টিনেশন ভার্টেক্স
break;
q.pop();
for (int j = v+1; j <= (v+6) && j < cell; ++j) { // পরের ১ থেকে ৬ সেলের জন্য
if (!visited[j]) {
vertex newVert;
newVert.dist = (qVert.dist + 1); // প্রাথমিকভাবে দূরত্ব ১ বাড়েছে
visited[j] = true;
if (move[j] != -1) // যদি j-তম জায়গায় স্নেক বা ল্যাডার থাকে
newVert.vert = move[j]; // সেখানে জাম্প করুন
else
newVert.vert = j;
q.push(newVert);
}
}
}
return qVert.dist; // ন্যূনতম ডাইস থ্রো এর সংখ্যা
}
int main() {
int cell = 30; // মনে করুন ৩০টি সেল আছে
int moves[cell];
for (int i = 0; i < cell; i++)
moves[i] = -1; // প্রাথমিকভাবে কোনো স্নেক বা ল্যাডার ইনিশিয়ালাইজ করা নেই
// ল্যাডারের জন্য সেল i-এ, এটি move[i]-এ জাম্প করে
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// স্নেকের জন্য সেল i-এ, এটি move[i]-এ জাম্প করে
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
cout << "Min Dice throws required is " << minDiceThrow(moves, cell);
}
আউটপুট
Min Dice throws required is 3
