मान लीजिए हमारे पास 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
