เส้นทางผลรวมสูงสุดในเมทริกซ์จากด้านบนลงล่างและกลับมาในโปรแกรม C++

ในปัญหานี้ เราได้รับเมทริกซ์ mat[][] ขนาด n x m ภารกิจของเราคือสร้างโปรแกรมเพื่อหาเส้นทางผลรวมสูงสุดในเมทริกซ์จากด้านบนลงล่างและกลับมาอีกครั้ง

คำอธิบายปัญหา

เราต้องการหาผลรวมเส้นทางสูงสุดจากมุมซ้ายบนไปยังมุมขวาล่าง และกลับมาอีกครั้ง

การเคลื่อนที่ที่ถูกต้อง

จาก 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 <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 << "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