พิมพ์เส้นทางทั้งหมดจากมุมซ้ายบนไปขวาล่างของเมทริกซ์ m×n ใน C++

ปัญหา

ได้รับเมทริกซ์ 2D ขนาด m×n พิมพ์เส้นทางทั้งหมดจากมุมซ้ายบน (0,0) ไปมุมขวาล่าง (m-1,n-1) เคลื่อนที่ได้แค่ Right และ Down

ตัวอย่าง

Input:
1 3 5
2 8 9
Output:
1 → 3 → 5 → 9
1 → 3 → 8 → 9
1 → 2 → 8 → 9

วิธีแก้

Recursive: จากเซลล์ปัจจุบัน เดิน Right และ Down พิมพ์เส้นทางเมื่อถึงขอบ

ตัวอย่างโค้ด

#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); // Down
    printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1); // Right
}

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;
}

ผลลัพธ์

1 4 5 6
1 2 5 6
1 2 3 6

คำอธิบาย

ฟังก์ชัน Recursive ส่ง path array และ index ปัจจุบัน (pi) เมื่อถึงแถวสุดท้ายหรือคอลัมน์สุดท้าย จะเติมส่วนที่เหลือและพิมพ์

จำนวนเส้นทางทั้งหมด = C(m+n-2, m-1) หรือ C(m+n-2, n-1)