এই সমস্যায়, আমাদের nXm আকারের একটি ম্যাট্রিক্স ম্যাট [][][] দেওয়া হয়েছে। আমাদের কাজ হল একটি ম্যাট্রিক্সে সর্বোচ্চ সমষ্টির পথ খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যা উপরে থেকে নীচে এবং পিছনে।
সমস্যা বর্ণনা − আমাদের উপরের বাম থেকে নীচের ডানদিকে এবং তারপরে পিছনের সর্বাধিক পথের যোগফল খুঁজে বের করতে হবে।
বৈধ পদক্ষেপগুলি
From mat[0][0] to mat[n−1][m−1]: Right (mat[i][j] to mat[i][j+1]) and Down (mat[i][j] to mat[i+1][j]). From mat[n−1][m−1] to mat[0][0]: left (mat[i][j] to mat[i][j−1]) and up (mat[i][j] to mat[i−1][j]).
একটি গুরুত্বপূর্ণ বিষয় হল উভয় পথ একই হতে পারে না। উভয় পথেই এক বা একাধিক উপাদান আলাদা হওয়া উচিত।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
mat[][] = {
{1, 2, 4},
{3, 0, 1},
{5, −1, −1}
} আউটপুট
15
ব্যাখ্যা
Path from mat[0][0] to mat[n−1][m−1]: 1 + 3 + 5 − 1 − 1 = 7 Path from mat[n−1][m−1] to mat[0][0]: + 1 + 4 + 2 + 1 = 8 Sum = 7 + 8 = 15
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের দুটি পথ খুঁজে বের করতে হবে (একটি ম্যাট[0][0] থেকে ম্যাট[n−1][m−1] এবং আরেকটি ম্যাট[n−1][m−1] থেকে ম্যাট পর্যন্ত[ 0][0])। কিন্তু একটি ভালো কাজ হল ম্যাট[0][0] থেকে ম্যাট[n− 1][m−1] পর্যন্ত দুটি ভিন্ন পথের জন্য একটি যোগফল খুঁজে বের করা। এর জন্য, আমরা ম্যাট[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
