C++ 프로그램에서 위에서 아래로 그리고 뒤로 행렬의 최대 합 경로

이 문제에서는 nXm 크기의 행렬 mat[][]가 제공됩니다. 우리의 임무는 위에서 아래로 그리고 그 반대로 행렬에서 최대 합 경로를 찾는 프로그램을 만드는 것입니다.

문제 설명 − 좌상단에서 우하단까지의 최대 경로 합을 찾아야 합니다.

유효한 움직임

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

솔루션 접근 방식

문제를 해결하려면 두 개의 경로를 찾아야 합니다(하나는 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