พิมพ์เส้นทางทั้งหมดจากมุมซ้ายบนไปขวาล่างใน Matrix อนุญาต 4 ทิศทางใน C++

ในปัญหานี้ เราจะได้รับ 2D matrix ขนาด mXn และต้องพิมพ์เส้นทางทั้งหมดที่เป็นไปได้จากมุมซ้ายบนไปมุมขวาล่างของ matrix สำหรับการท่อง เราสามารถเคลื่อนที่ได้ 4 ทิศทาง คือ ซ้าย ขวา บน ล่าง

แม้การเคลื่อนที่ขวาและบนจะนادرใช้แต่บางครั้งก็มีประโยชน์

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

Input:

1 3 5
2 8 9

Output:

1 → 3 → 5 → 9
1 → 3 → 8 → 9
1 → 2 → 8 → 9

เพื่อแก้ปัญหานี้ เราจะเคลื่อนจาก cell หนึ่งไปอีก cell และพิมพ์ path เมื่อลงและขวา เราจะทำแบบ recursive สำหรับแต่ละ cell ใน matrix

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

#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-right of matrix are :\n";
    findPath(*mat, 2, 3);
    return 0;
}

ผลลัพธ์

Path from top-left to bottom-right of matrix are :
1 4 5 6
1 2 5 6
1 2 3 6