Giả sử chúng ta có một ma trận vuông bậc n. Nó có tất cả các yếu tố riêng biệt. Vì vậy, chúng ta phải tìm đường đi có độ dài lớn nhất, sao cho tất cả các ô dọc theo đường dẫn có thứ tự tăng dần với hiệu số là 1. Từ một ô, chúng ta có thể di chuyển đến bốn hướng. Trái, phải, trên và dưới. Vì vậy, nếu ma trận giống như -
| 1 | 2 | 9 |
| 5 | 3 | 8 |
| 4 | 6 | 7 |
Vì vậy, đầu ra sẽ là 4. Vì con đường dài nhất là 6 → 7 → 8 → 9
Để giải quyết vấn đề này, chúng ta sẽ theo dõi ý tưởng này. Chúng tôi sẽ tính toán đường dẫn dài nhất bắt đầu với mỗi ô. Khi chúng tôi đã có đường dẫn dài nhất cho tất cả các ô, chúng tôi trả về tối đa tất cả các đường dẫn dài nhất.
Một nhận xét quan trọng trong cách tiếp cận này là nhiều vấn đề phụ chồng chéo. Vì vậy, vấn đề này có thể được giải quyết bằng cách sử dụng Lập trình động. Ở đây, chúng tôi sẽ sử dụng bảng tra cứu dp [] [] để kiểm tra xem sự cố đã được giải quyết hay chưa.
Ví dụ
#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);
} Đầu ra
Length of the longest path is 4