Tìm đường đi có tổng lớn nhất trong ma trận từ trên xuống dưới và ngược lại bằng C++

Trong bài toán này, chúng ta được cung cấp một ma trận mat[][] kích thước n x m. Nhiệm vụ là viết chương trình tìm đường đi có tổng lớn nhất trong ma trận từ góc trên bên trái đến góc dưới bên phải và quay lại.

Mô tả bài toán

Chúng ta cần tìm tổng đường đi lớn nhất từ mat[0][0] đến mat[n-1][m-1] và sau đó quay về mat[0][0].

Các bước di chuyển hợp lệ

Từ mat[0][0] đến mat[n-1][m-1]: Sang phải (mat[i][j] đến mat[i][j+1]) và Xuống (mat[i][j] đến mat[i+1][j]).
Từ mat[n-1][m-1] về mat[0][0]: Sang trái (mat[i][j] đến mat[i][j-1]) và Lên (mat[i][j] đến mat[i-1][j]).

Một điểm quan trọng: hai đường đi không được giống nhau hoàn toàn. Phải có ít nhất một phần tử khác biệt giữa hai đường đi.

Ví dụ minh họa

Đầu vào

mat[][] = { {1, 2, 4}, 
            {3, 0, 1}, 
            {5, -1, -1} }

Đầu ra

15

Giải thích

Đường đi từ mat[0][0] đến mat[n-1][m-1]: 1 + 3 + 5 - 1 - 1 = 7
Đường đi từ mat[n-1][m-1] về mat[0][0]: 1 + 4 + 2 + 1 = 8
Tổng = 7 + 8 = 15

Phương pháp giải

Để giải bài toán, chúng ta cần tìm hai đường đi (một từ mat[0][0] đến mat[n-1][m-1] và một đường ngược lại). Cách tốt hơn là tìm tổng của hai đường đi khác nhau từ mat[0][0] đến mat[n-1][m-1]. Chúng ta bắt đầu từ mat[0][0] và tìm hai đường đi bằng cách chọn các phần tử tiềm năng nhất cho đến khi cả hai đều đến đích. Sau đó trả về tổng của cả hai. Cần kiểm tra để đảm bảo không có ô nào nằm trên cả hai đường đi (vì yêu cầu hai đường đi phải khác nhau).

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

#define ROW 3

int CalcNodeDiff(int mat[][ROW], int path1x, int path1y, int path2x, int path2y) {
    if (path1x == path2x && path1y == path2y) {
        return mat[path1x][path1y];
    }
    return mat[path1x][path1y] + mat[path2x][path2y];
}

int calcMaxPathSumOfMat(int mat[][ROW], int path1x, int path1y, int path2x, int n) {
    int pathSumDP[5][5][5];
    memset(pathSumDP, -1, sizeof(pathSumDP));
    
    int path2y = path1x + path1y - path2x;
    int maxPathSum = -10000;
    
    if (path1x >= n || path2x >= n || path1y >= ROW || path2y >= ROW)
        return 0;
    
    if (pathSumDP[path1x][path1y][path2x] != -1)
        return pathSumDP[path1x][path1y][path2x];
    
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    
    pathSumDP[path1x][path1y][path2x] = maxPathSum;
    return maxPathSum;
}

int main() {
    int n = 3;
    int mat[n][ROW] = {
        { 1, 2, 4 },
        { 3, 0, 1 },
        { 5, -1, -1 }
    };
    cout << "Tổng đường đi lớn nhất trong ma trận từ trên xuống dưới và ngược lại là "
         << calcMaxPathSumOfMat(mat, 0, 0, 0, n);
    return 0;
}

Đầu ra

Tổng đường đi lớn nhất trong ma trận từ trên xuống dưới và ngược lại là 15