พิมพ์ Palindromic Paths จากมุมซ้ายบนไปขวาล่างใน Matrix ใน C++

ในปัญหานี้ เราจะได้รับ matrix ที่มีตัวอักษร (lowercase only) และต้องพิมพ์ palindromic paths ทั้งหมดใน matrix ที่กำหนดจากมุมซ้ายบนไปมุมขวาล่างของ matrix

การเคลื่อนไหวที่อนุญาตในปัญหานี้คือ ขวา และ ลง ไม่อนุญาตให้เคลื่อนย้อนกลับหรือทแยง

ตัวอย่างเพื่อความเข้าใจ

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

คำอธิบาย

มาดู valid moves ทั้งหมดจากมุมซ้ายบนไปขวาล่างโดยใช้ position เทียบกับ i-th position

i00 → i01 → i02 → i03 → i13 → i23 = xxxyxx
i00 → i01 → i11 → i12 → i13 → i23 = xxxxxx
...
i00 → i10 → i20 → i21 → i22 → i23 = xyxyyx

จากผลลัพธ์ทั้งหมด เราต้องการเฉพาะ palindromic path เป็น outcomes:

i00 → i01 → i11 → i12 → i13 → i23 = xxxxxx
i00 → i01 → i02 → i12 → i13 → i23 = xxxxxx
i00 → i10 → i11 → i12 → i22 → i23 = xyxxyx

ในคำอธิบายเอง เราได้วางฐานของคำตอบแล้ว เราจะหา paths ทั้งหมดจาก top-left ไป bottom-right และพิมพ์เฉพาะที่ให้ผลลัพธ์เป็น palindromic path

โปรแกรมตัวอย่าง

#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 << "Palindromic path are : ";
    findPath(str, matrix, 0, 0, 4, 3);
    return 0;
}

ผลลัพธ์

Palindromic path are : xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx