Cho ma trận m x n, in tất cả đường đi từ (0,0) đến (m-1,n-1). Cho phép đi 4 hướng: trái, phải, lên, xuống.
Ví dụ:
Input: 1 3 5
2 8 9
Output: 1->3->5->9; 1->3->8->9; 1->2->8->9
Giải pháp: Đệ quy từ mỗi ô, thử 4 hướng (tránh quay lại ô vừa đến). In đường đi khi đến đích.
Chương trình minh họa
#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 << "Đường đi từ trên trái đến dưới phải:\n";
findPath(*mat, 2, 3);
return 0;
}
Kết quả
1 4 5 6 1 2 5 6 1 2 3 6