इस समस्या में, हमें 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] से चटाई [एन -1] [एम -1] और दूसरा मैट [एन -1] [एम -1] से मैट [ 0 [0])। लेकिन एक बेहतर बात यह है कि मैट [0] [0] से मैट [एन− 1] [एम -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