สมมติว่าเรามีเมทริกซ์กำลังสองของลำดับ n มีองค์ประกอบที่แตกต่างกันทั้งหมด ดังนั้นเราจึงต้องหาเส้นทางที่มีความยาวสูงสุด เพื่อให้เซลล์ทั้งหมดบนเส้นทางมีลำดับเพิ่มขึ้นโดยมีผลต่าง 1 จากเซลล์หนึ่ง เราสามารถย้ายไปยังสี่ทิศทางได้ ซ้าย ขวา บน และล่าง ดังนั้นหากเมทริกซ์เป็นเหมือน −
| 1 | 2 | 9 |
| 5 | 3 | 8 |
| 4 | 6 | 7 |
ดังนั้นผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางที่ยาวที่สุดคือ 6→7→8→ 9
เพื่อแก้ปัญหานี้ เราจะทำตามแนวคิดนี้ เราจะคำนวณเส้นทางที่ยาวที่สุดโดยเริ่มจากทุกเซลล์ เมื่อเราได้เซลล์ที่ยาวที่สุดแล้ว เราจะคืนค่าเส้นทางที่ยาวที่สุดทั้งหมด
การสังเกตที่สำคัญอย่างหนึ่งในแนวทางนี้คือปัญหาย่อยที่ทับซ้อนกันมากมาย ดังนั้นปัญหานี้สามารถแก้ไขได้โดยใช้ Dynamic Programming ที่นี่เราจะใช้ตารางการค้นหา 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
