Trong bài toán này, chúng ta được cung cấp một ma trận 2D mXn và chúng ta phải in tất cả các đường có thể có từ trên cùng bên trái đến dưới cùng bên phải của ma trận. Đối với tính năng duyệt, chúng ta chỉ có thể di chuyển sang phải và xuống trong ma trận.
Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -
Input: 1 3 5 2 8 9 Output: 1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9
Để giải quyết vấn đề này, chúng ta sẽ di chuyển từ ô này sang ô khác và in đường dẫn đi xuống và sang phải. Chúng tôi sẽ thực hiện điều này một cách đệ quy cho từng ô trong thematrix.
Ví dụ
Hãy xem một chương trình triển khai thuật toán đệ quy:
#include<iostream>
using namespace std;
void printPathTPtoBR(int *mat, int i, int j, int m, int n, int *path, int pi) {
if (i == m - 1){
for (int k = j; k < n; k++)
path[pi + k - j] = *((mat + i*n) + k);
for (int l = 0; l < pi + n - j; l++)
cout << path[l] << " ";
cout << endl;
return;
}
if (j == n - 1){
for (int k = i; k < m; k++)
path[pi + k - i] = *((mat + k*n) + j);
for (int l = 0; l < pi + m - i; l++)
cout << path[l] << " ";
cout << endl;
return;
}
path[pi] = *((mat + i*n) + j);
printPathTPtoBR(mat, i+1, j, m, n, path, pi + 1);
printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1);
}
void findPath(int *mat, int m, int n) {
int *path = new int[m+n];
printPathTPtoBR(mat, 0, 0, m, n, path, 0);
}
int main() {
int mat[2][3] = { {1, 2, 3}, {4, 5, 6} };
cout<<"Path from top-left to bottom-rigth of matrix are :\n";
findPath(*mat, 2, 3);
return 0;
} Đầu ra
Đường dẫn từ trên cùng bên trái đến dưới cùng bên phải của ma trận là -
1 4 5 6 1 2 5 6 1 2 3 6