मान लीजिए कि हमारे पास ऑर्डर n का एक वर्ग मैट्रिक्स है। इसमें सभी विशिष्ट तत्व हैं। इसलिए हमें अधिकतम लंबाई पथ ज्ञात करना है, जैसे कि पथ के साथ सभी कोशिकाएं 1 के अंतर के साथ बढ़ते क्रम में हैं। एक सेल से हम चार दिशाओं में जा सकते हैं। बाएँ, दाएँ, ऊपर और नीचे। तो अगर मैट्रिक्स की तरह है -
| 1 | 2 | 9 |
| 5 | 3 | 8 |
| 4 | 6 | 7 |
तो आउटपुट 4 होगा। चूंकि सबसे लंबा रास्ता 6→7→8→ 9
. हैइस समस्या को हल करने के लिए, हम इस विचार का पालन करेंगे। हम प्रत्येक सेल से शुरू होने वाले सबसे लंबे पथ की गणना करेंगे। एक बार जब हमें सभी सेल के लिए सबसे लंबा रास्ता मिल जाता है, तो हम अधिकतम सभी सबसे लंबे पथ लौटाते हैं।
इस दृष्टिकोण में एक महत्वपूर्ण अवलोकन कई अतिव्यापी उप-समस्याएं हैं। इसलिए डायनेमिक प्रोग्रामिंग का उपयोग करके इस समस्या को हल किया जा सकता है। यहां हम एक लुकअप टेबल dp[][] का उपयोग यह जांचने के लिए करेंगे कि कोई समस्या पहले ही हल हो चुकी है या नहीं।
उदाहरण
#include <iostream>
#define n 3
using namespace std;
int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) {
if (i < 0 || i >= n || j < 0 || j >= n)
return 0;
if (table[i][j] != -1)
return table[i][j];
int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table);
if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table);
if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table);
if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table);
return table[i][j] = max(x, max(y, max(z, max(w, 1))));
}
int getLongestPathLength(int matrix[n][n]) {
int result = 1;
int table[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
table[i][j] = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (table[i][j] == -1)
getLongestPathLengthUtil(i, j, matrix, table);
result = max(result, table[i][j]);
}
}
return result;
}
int main() {
int mat[n][n] = { { 1, 2, 9 },
{ 5, 3, 8 },
{ 4, 6, 7 } };
cout << "Length of the longest path is "<< getLongestPathLength(mat);
} आउटपुट
Length of the longest path is 4