विभिन्न वर्णों का एक मैट्रिक्स दिया गया है। एक वर्ण से शुरू करके हमें सबसे लंबा पथ ढूंढना है जो उन सभी वर्णों को पार करके जाता है जो वर्तमान वर्ण से बड़े हैं। वर्ण एक-दूसरे के क्रमागत हैं।
E से शुरू होता है।
सबसे लंबा पथ ढूंढने के लिए, हम डेप्थ फर्स्ट सर्च एल्गोरिदम का उपयोग करेंगे। DFS के दौरान, कुछ उप-समस्याएं कई बार उत्पन्न हो सकती हैं। उन उप-समस्याओं की गणना को बार-बार रोकने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
उदाहरण
#include<iostream> #define ROW 3 #define COL 3 using namespace std; // tool matrices to recur for adjacent cells. int x[] = {0, 1, 1, -1, 1, 0, -1, -1}; int y[] = {1, 0, 1, 1, -1, -1, 0, -1}; int longestPath[ROW][COL]; char mat[ROW][COL] = { {'a','c','d'}, {'h','b','a'}, {'i','g','f'} }; int max(int a, int b){ return (a>b)?a:b; } bool isvalid(int i, int j){ if (i < 0 || j < 0 || i >= ROW || j >= COL) return false; return true; } bool isadjacent(char previous, char current){ return ((current - previous) == 1); //check current and previous are adjacent or not } int findLongestLen(int i, int j, char prev){ if (!isvalid(i, j) || !isadjacent(prev, mat[i][j])) return 0; if (longestPath[i][j] != -1) return longestPath[i][j]; //subproblems are solved already int len = 0; // Initialize result to 0 for (int k=0; k<8; k++) //find length of the largest path recursively len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j])); return longestPath[i][j] = len; // save the length and return } int getLen(char start){ for(int i = 0; i<ROW; i++) for(int j = 0; j<COL; j++) longestPath[i][j] = -1; //set all elements to -1 int len = 0; for (int i=0; i<ROW; i++){ for (int j=0; j<COL; j++){ // check for all possible starting point if (mat[i][j] == start) { for (int k=0; k<8; k++) //for all eight adjacent cells len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start)); } } } return len; } int main() { char start; cout << "Enter Starting Point (a-i): "; cin >> start; cout << "Maximum consecutive path: " << getLen(start); return 0; } आउटपुट
Enter Starting Point (a-i): e Maximum consecutive path: 5
