ধরুন আমাদের ক্রম 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
