इस समस्या में, हमें n×m आकार का एक मैट्रिक्स mat[][] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो मैट्रिक्स में ऊपर से नीचे और वापस आने का अधिकतम योग पथ ढूंढे।
समस्या विवरण
हमें ऊपरी-बाएं (top-left) से निचले-दाएं (bottom-right) तक और फिर वापस आने का अधिकतम पथ योग ढूंढना है।
मान्य चालें (Valid Moves)
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
