अवधारणा
दिए गए संख्याओं के ग्रिड के संबंध में, अधिकतम लंबाई स्नेक अनुक्रम निर्धारित करें और प्रदर्शित करें। यह देखा गया है कि यदि अधिकतम लंबाई के साथ कई स्नेक अनुक्रम मौजूद हैं, तो उनमें से किसी एक को प्रदर्शित करें।
वास्तव में, एक स्नेक अनुक्रम ग्रिड में आसन्न संख्याओं से बना होता है ताकि प्रत्येक संख्या के लिए, दाईं ओर की संख्या या नीचे की संख्या उसके मान से +1 या -1 हो। यहां, उदाहरण के लिए, यदि हम ग्रिड में स्थान (a, b) पर हैं, तो हम या तो दाईं ओर जा सकते हैं यानी (a, b+1) यदि वह संख्या ±1 है या नीचे जा सकते हैं यानी (a+1, b) यदि वह संख्या ±1 है।
उदाहरण के लिए,
10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8
उपरोक्त ग्रिड में, अधिकतम स्नेक अनुक्रम है: (10, 9, 8, 7, 6, 7, 8)
नीचे दिए गए चित्र में सभी संभावित पथ दिखाए गए हैं −
10 7 →6 3 ↓ ↓ ↓ 9 → 8 → 7→ 6 ↓↓ 8 4 2 7 ↓ 2 2 2 8
विधि
यहां, अवधारणा डायनामिक प्रोग्रामिंग लागू करना है। मैट्रिक्स के प्रत्येक सेल के संबंध में, हम वर्तमान सेल में समाप्त होने वाले स्नेक की सबसे लंबी लंबाई रखते हैं। अब सबसे लंबी लंबाई वाला स्नेक अनुक्रम अधिकतम मान रखेगा। यहां, सबसे लंबा मान वाला सेल स्नेक की पूंछ से मेल खाएगा। स्नेक को प्रिंट करने के लिए, हमें पूंछ से वापस स्नेक के सिर तक बैकट्रैक करने की आवश्यकता है। मान लें T[a][b] सेल (a, b) पर समाप्त होने वाले स्नेक की अधिकतम लंबाई को दर्शाता है, तो दी गई मैट्रिक्स M के लिए, डायनामिक प्रोग्रामिंग संबंध इस प्रकार परिभाषित किया गया है −
T[0][0] = 0 T[a][b] = max(T[a][b], T[a][b – 1] + 1) if M[a][b] = M[a][b – 1] ± 1 T[a][b] = max(T[a][b], T[a – 1][b] + 1) if M[a][b] = M[a – 1][b] ± 1
उदाहरण
// C++ program to find maximum length // Snake sequence and print it #include <bits/stdc++.h> using namespace std; #define M 4 #define N 4 struct Point{ int X, Y; }; // अधिकतम लंबाई स्नेक अनुक्रम पथ खोजने वाला फ़ंक्शन // (a, b) स्नेक की पूंछ से मेल खाता है list<Point> findPath(int grid1[M][N], int mat1[M][N], int a, int b){ list<Point> path1; Point pt1 = {a, b}; path1.push_front(pt1); while (grid1[a][b] != 0){ if (a > 0 && grid1[a][b] - 1 == grid1[a - 1][b]){ pt1 = {a - 1, b}; path1.push_front(pt1); a--; } else if (b > 0 && grid1[a][b] - 1 == grid1[a][b - 1]){ pt1 = {a, b - 1}; path1.push_front(pt1); b--; } } return path1; } // अधिकतम लंबाई स्नेक अनुक्रम खोजने वाला फ़ंक्शन void findSnakeSequence(int mat1[M][N]){ // उपसमस्याओं के परिणाम संग्रहीत करने के लिए टेबल दिखाता है int lookup1[M][N]; // 0 से इनिशियलाइज़ करने के लिए उपयोग किया जाता है memset(lookup1, 0, sizeof lookup1); // स्नेक अनुक्रम की अधिकतम लंबाई संग्रहीत करने के लिए उपयोग किया जाता है int max_len1 = 0; // स्नेक की पूंछ के निर्देशांक संग्रहीत करने के लिए उपयोग किया जाता है int max_row1 = 0; int max_col1 = 0; // बॉटम-अप फैशन में टेबल भरने के लिए उपयोग किया जाता है for (int a = 0; a < M; a++){ for (int b = 0; b < N; b++){ // (0, 0) सेल को छोड़कर प्रदर्शन करें if (a || b){ // ऊपर देखें if (a > 0 && abs(mat1[a - 1][b] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a - 1][b] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } // बाएं देखें if (b > 0 && abs(mat1[a][b - 1] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a][b - 1] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } } } } cout << "Maximum length of Snake sequence is: " << max_len1 << endl; // अधिकतम लंबाई स्नेक अनुक्रम पथ निर्धारित करें list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1); cout << "Snake sequence is:"; for (auto it = path1.begin(); it != path1.end(); it++) cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;} // ड्राइवर कोड int main(){ int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8},}; findSnakeSequence(mat1); return 0; }आउटपुट
Maximum length of Snake sequence is: 6 Snake sequence is: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)