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

Cho ma trận m×n, in tất cả đường đi từ (0,0) đến (m-1,n-1) chỉ đi xuống (down) hoặc phải (right).

Ví dụ

Ma trận 2×3: 1 2 3 4 5 6

Các đường đi: 1→2→3→6, 1→2→5→6, 1→4→5→6

Thuật toán đệ quy

Tại ô (i,j): thêm vào path, đệ quy (i+1,j) và (i,j+1). Khi đến hàng cuối/cột cuối, điền thẳng đến đích.

Chương trình mẫu

#include <iostream>
using namespace std;

void printPath(int *mat, int i, int j, int m, int n, int *path, int pi) {
    if (i == m - 1) { // Hàng cuối: chỉ đi phải
        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) { // Cột cuối: chỉ đi xuống
        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);
    printPath(mat, i + 1, j, m, n, path, pi + 1); // Đi xuống
    printPath(mat, i, j + 1, m, n, path, pi + 1); // Đi phải
}

void findPath(int *mat, int m, int n) {
    int *path = new int[m + n];
    printPath(mat, 0, 0, m, n, path, 0);
    delete[] path;
}

int main() {
    int mat[2][3] = {{1, 2, 3}, {4, 5, 6}};
    cout << "Paths from top-left to bottom-right:\n";
    findPath(*mat, 2, 3);
    return 0;
}

Kết quả

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

Độ phức tạp: O(C(m+n-2, m-1) × (m+n)) thời gian (số đường đi × độ dài path), O(m+n) stack space.

Số đường đi: C(m+n-2, m-1) = (m+n-2)!/((m-1)!(n-1)!).