सांप और सीढ़ी समस्या

हम प्रसिद्ध खेल सांप और सीढ़ी के बारे में जानते हैं। इस खेल में, बोर्ड पर कुछ कमरे होते हैं, कमरा संख्या के साथ। कुछ कमरे सीढ़ी या सांप से जुड़े होते हैं। जब हमें सीढ़ी मिलती है, तो हम क्रमिक रूप से आगे बढ़े बिना गंतव्य के निकट पहुंचने के लिए कुछ कमरों तक चढ़ सकते हैं। इसी तरह, जब हमें कुछ सांप मिलता है, तो यह हमें एक निचले कमरे में भेज देता है ताकि हम उस कमरे से फिर से यात्रा शुरू कर सकें।

इस समस्या में, हमें प्रारंभ से गंतव्य तक पहुंचने के लिए आवश्यक पासा फेंक की न्यूनतम संख्या ढूंढनी है।

इनपुट और आउटपुट

इनपुट: सांप और सीढ़ी के प्रारंभिक और अंतिम स्थान। सांप: 26 से 0, 20 से 8, 16 से 3, 18 से 6 सीढ़ी: 2 से 21, 4 से 7, 10 से 25, 19 से 28 आउटपुट: आवश्यक न्यूनतम पासा फेंक 3 है

एल्गोरिदम

minDiceThrow(move, cell)

इनपुट: सांप या सीढ़ी के लिए कूद स्थान, और कुल सेल की संख्या।
आउटपुट: अंतिम सेल तक पहुंचने के लिए आवश्यक न्यूनतम पासा फेंक की संख्या।

शुरू     प्रारंभ में सभी सेल को अनदेखा चिह्नित करें     कतार q परिभाषित करें     प्रारंभिक शीर्ष को देखा गया चिह्नित करें     प्रारंभिक शीर्ष के लिए शीर्ष संख्या := 0 और दूरी := 0     प्रारंभिक शीर्ष s को q में जोड़ें     जब तक q खाली नहीं है, करें       qVert := कतार का सामने का तत्व       v := qVert की शीर्ष संख्या       यदि v = cell -1, तो //जब यह अंतिम शीर्ष है         लूप तोड़ें       कतार से एक आइटम हटाएं       j := v + 1, से v + 6 और j < cell, j को 1 से बढ़ाकर, करें         यदि j नहीं देखा गया है, तो           newVert.dist := (qVert.dist + 1)           v को देखा गया चिह्नित करें           यदि सांप या सीढ़ी है, तो             newVert.vert := move[j] //उस स्थान पर कूदें           अन्यथा             newVert.vert := j           newVert को कतार में डालें         किया       किया     किया     qVert.dist वापस करें अंत

उदाहरण

#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;       //प्रारंभ में 0 से शुरू     vertex s = {0, 0};     q.push(s);       // 0वें शीर्ष को एनक्यू करें     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
आउटपुट
Min Dice throws required is 3