Trong bài toán này, chúng ta được cung cấp một matix chứa các aplhabet (chỉ viết thường) và chúng ta phải in tất cả các đường dẫn palidromic trong ma trận đã cho từ trên cùng bên trái đến dưới cùng bên phải của ma trận.
Di chuyển được phép trong vấn đề này là phải và xuống. Di chuyển theo đường chéo không được phép.
Hãy lấy một ví dụ để hiểu vấn đề -
Input: matrix[][] ={
{"xxxy",
"yxxx",
"xyyx"}
Output: xxxxxx , xxxxxx , xyxxyx Giải thích
Cho phép xem tất cả các bước di chuyển hợp lệ từ trên cùng bên trái sang dưới cùng bên phải bằng cách sử dụng vị trí wrt đến thứ i vị trí.
i00 -> i01 -> i02 -> i03 -> i13 -> i23 = xxxyxx i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx . . . i00 -> i10 -> i20 -> i21 -> i22 -> i23 = xyxyyx
Trong số tất cả các kết quả có thể có, chúng ta chỉ cần con đường palindromic là các kết quả -
i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx i00 -> i01 -> i02 -> i12 -> i13 -> i23 = xxxxxx i00 -> i10 -> i11 -> i12 -> i22 -> i23 = xyxxyx
Trong phần giải thích, chúng tôi đã đặt ra cơ sở của giải pháp cho vấn đề. Chúng tôi sẽ tìm tất cả các đường dẫn từ trên cùng bên trái đến dưới cùng bên phải và in tất cả những đường dẫn đưa ra kết quả cho đường dẫn palindromic.
Ví dụ
Ví dụ dưới đây sẽ minh họa giải pháp -
#include<iostream>
using namespace std;
#define N 4
int printPalindrome(string str){
int len = str.length() / 2;
for (int i = 0; i < len; i++) {
if (str[i] != str[str.length() - i - 1])
return 0;
}
cout<<str<<endl;
}
void findPath(string str, char a[][N], int i, int j, int m, int n) {
if (j < m - 1 || i < n - 1) {
if (i < n - 1)
findPath(str + a[i][j], a, i + 1, j, m, n);
if (j < m - 1)
findPath(str + a[i][j], a, i, j + 1, m, n);
} else {
str = str + a[n - 1][m - 1];
printPalindrome(str) ;
}
}
int main() {
char matrix[][N] = {
{ 'x', 'y', 'x', 'y' },
{ 'y', 'x', 'x', 'y' },
{ 'y', 'x', 'y', 'x' }
};
string str = "";
cout<<"Palimdromic path are : ";
findPath(str, matrix, 0, 0, 4, 3);
return 0;
} Đầu ra
Palimdromic path are : xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx