ম্যাট্রিক্সে উপরে থেকে নিচে এবং আবার উপরে ফিরে আসার সর্বোচ্চ যোগফল পথ (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের একটি n×m আকারের ম্যাট্রিক্স mat[][] দেওয়া আছে। আমাদের কাজ হল ম্যাট্রিক্সে উপরের বাম কোণ (mat[0][0]) থেকে নিচের ডান কোণ (mat[n-1][m-1]) পর্যন্ত এবং আবার নিচের ডান কোণ থেকে উপরের বাম কোণে ফিরে আসার সর্বোচ্চ যোগফল পথ খুঁজে বের করা।

আমাদের mat[0][0] থেকে mat[n-1][m-1] পর্যন্ত এবং তারপর আবার mat[n-1][m-1] থেকে mat[0][0] পর্যন্ত ফিরে আসার সর্বোচ্চ পথ যোগফল খুঁজে বের করতে হবে।

• mat[0][0] থেকে mat[n-1][m-1] পর্যন্ত: ডান (mat[i][j] থেকে mat[i][j+1]) এবং নিচে (mat[i][j] থেকে mat[i+1][j])
• mat[n-1][m-1] থেকে mat[0][0] পর্যন্ত: বাম (mat[i][j] থেকে mat[i][j-1]) এবং উপরে (mat[i][j] থেকে mat[i-1][j])

গুরুত্বপূর্ণ শর্ত: দুটি পথ একই হতে পারবে না। দুটি পথে কমপক্ষে একটি উপাদান ভিন্ন থাকতে হবে।

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

15

mat[0][0] থেকে mat[n-1][m-1] পর্যন্ত পথ: 1 + 3 + 5 - 1 - 1 = 7
mat[n-1][m-1] থেকে mat[0][0] পর্যন্ত পথ: 1 + 4 + 2 + 1 = 8
মোট যোগফল = 7 + 8 = 15

এই সমস্যা সমাধানের জন্য, আমরা দুটি পথ খুঁজে বের করতে পারি (একটি mat[0][0] থেকে mat[n-1][m-1] এবং অন্যটি mat[n-1][m-1] থেকে mat[0][0])। কিন্তু আরও ভালো পদ্ধতি হল mat[0][0] থেকে mat[n-1][m-1] পর্যন্ত দুটি ভিন্ন পথের যোগফল খুঁজে বের করা। এর জন্য, আমরা mat[0][0] থেকে শুরু করে দুটি পথ খুঁজে বের করব পরবর্তী সবচেয়ে आशाजনক উপাদানগুলো বেছে নিয়ে যতক্ষণ না পথের শেষে পৌঁছান। তারপর দুটি পথের যোগফল ফেরত দিব। একটি জিনিস চেক করতে হবে যে কোনো সেল দুটি পথে একসাথে নেই, কারণ দুটি ভিন্ন পথ থাকতে হবে।

#include 
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 << "The maximum sum path in a matrix from top to bottom and back is "
         << calcMaxPathSumOfMat(mat, 0, 0, 0, n);
    return 0;
}

The maximum sum path in a matrix from top to bottom and back is 15