Advertisement
jayati

Maximum path sum in matrix

Feb 12th, 2024
780
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. //{ Driver Code Starts
  2. // Initial Template for C++
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // } Driver Code Ends
  8. // User function Template for C++
  9.  
  10. class Solution{
  11. public:
  12.     int maximumPath(int N, vector<vector<int>> Matrix)
  13.     {
  14.         // code here
  15.         int n=N;
  16.         for(int i=1;i<n;i++)
  17.         {
  18.             for(int j=0;j<n;j++)
  19.             {
  20.                 if(j>0 && j<n-1)
  21.                 {
  22.                     Matrix[i][j]+=max({Matrix[i-1][j],Matrix[i-1][j-1],Matrix[i-1][j+1]});
  23.                 }
  24.                 else if(j>0)
  25.                 {
  26.                     Matrix[i][j]+=max(Matrix[i-1][j],Matrix[i-1][j-1]);
  27.                 }
  28.                 else if(j<n-1)
  29.                 {
  30.                     Matrix[i][j]+=max(Matrix[i-1][j],Matrix[i-1][j+1]);
  31.                 }
  32.             }
  33.         }
  34.         int ans=0;
  35.         for(int j=0;j<n;j++)
  36.         {
  37.             ans = max(Matrix[n-1][j],ans);
  38.         }
  39.         return ans;
  40.     }
  41. };
  42.  
  43. //{ Driver Code Starts.
  44.  
  45. int main(){
  46.     int t;
  47.     cin>>t;
  48.     while(t--){
  49.         int N;
  50.         cin>>N;
  51.         vector<vector<int>> Matrix(N, vector<int>(N, 0));
  52.         for(int i = 0;i < N*N;i++)
  53.             cin>>Matrix[(i/N)][i%N];
  54.        
  55.         Solution ob;
  56.         cout<<ob.maximumPath(N, Matrix)<<"\n";
  57.     }
  58.     return 0;
  59. }
  60. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement