Đường dẫn tổng tối đa trong ma trận từ trên xuống dưới và trở lại trong Chương trình C ++

Trong bài toán này, chúng ta đưa ra một ma trận [] [] có kích thước nXm. Nhiệm vụ của chúng ta là tạo một chương trình để tìm đường dẫn tổng lớn nhất trong một ma trận từ trên xuống dưới và ngược lại.

Mô tả sự cố - Chúng ta cần tìm tổng đường dẫn lớn nhất từ ​​trên trái xuống dưới cùng bên phải rồi quay lại.

Di chuyển hợp lệ

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]).

Một điều quan trọng là cả hai con đường không thể giống nhau. Phải có một hoặc nhiều phần tử khác nhau trong cả hai đường dẫn.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

mat[][] = {
   {1, 2, 4},
   {3, 0, 1},
   {5, −1, −1}
}

Đầu ra

15

Giải thích

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần tìm hai đường đi (một từ mat [0] [0] đến mat [n − 1] [m − 1] và một đường khác từ mat [n − 1] [m − 1] đến mat [ 0] [0]). Nhưng một điều tốt hơn nên làm là tìm một tổng cho hai đường đi khác nhau từ mat [0] [0] đến mat [n− 1] [m − 1]. Đối với điều này, chúng tôi sẽ bắt đầu từ mat [0] [0] và tìm hai con đường bằng cách tìm các phần tử tiếp theo có triển vọng nhất cho đến khi chúng đi đến cuối con đường. Sau đó trả về tổng của cả hai. Một điều chúng ta cần kiểm tra là tìm xem một ô không nằm trên cả hai đường dẫn vì cần phải có hai đường dẫn khác nhau.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum sum path in a matrix from top to bottom and back is 15