विभिन्न वर्णों का एक मैट्रिक्स दिया गया है। एक चरित्र से शुरू करते हुए हमें उन सभी पात्रों को पार करके सबसे लंबा रास्ता खोजना होगा जो वर्तमान चरित्र से बड़े हैं। वर्ण एक दूसरे के क्रमागत होते हैं।
ई से शुरू होता है।
सबसे लंबा रास्ता खोजने के लिए, हम डेप्थ फर्स्ट सर्च एल्गोरिथम का उपयोग करेंगे। 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) //when i and j are in range
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]))
//when already included or not adjacent
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