In tất cả đường đi palindrome từ góc trên trái đến góc dưới phải trong ma trận C++

Cho ma trận chữ cái thường. In tất cả đường đi từ (0,0) đến (m-1,n-1) tạo thành palindrome. Chỉ cho phép đi phải hoặc xuống.

Input: matrix = {{"xxxy", "yxxx", "xyyx"}}
Output: xxxxxx, xxxxxx, xyxxyx

Giải pháp: DFS đệ quy thử 2 hướng (phải, xuống). Khi đến đích, kiểm tra chuỗi có phải palindrome không.

Chương trình minh họa

#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 << "Các đường đi palindrome:\n";
    findPath(str, matrix, 0, 0, 4, 3);
    return 0;
}

Kết quả

xyxxyx (lặp nhiều lần do trùng đường đi)