Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.6 kB
2
Indexable
Never
int getmaximum(vector<string>mat){
      int n = mat.size();
      int grid[n+2][n+2];
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  if(mat[i][j]=='*'){grid[i][j]=0;}
                  else if(mat[i][j]=='$'){grid[i][j]=1;}
                  else{grid[i][j]=-1;}
            }
      }
      if(grid[0][0]==-1 || grid[n-1][n-1]==-1){return 0;}
        vector<vector<int>> dp(n, vector<int>(n, -1));

        dp[0][0] = grid[0][0];
        
        const int maxi = 2 * (n - 1); 
        
        for (int k = 1; k <= maxi; k++) { 
            vector<vector<int>> curr(n, vector<int>(n, -1));
        
            for (int i = 0; i < n && i <= k; i++) {
                if ( k - i >= n) continue;
                for (int j = 0; j < n && j <= k; j++) {
                    if (k - j >= n) continue;
                    if (grid[i][k - i] < 0 || grid[j][k - j] < 0) { 
                        continue;
                    }
                    
                    int cherries = dp[i][j]; 
                    
                    if (i > 0) cherries = max(cherries, dp[i - 1][j]);
                    if (j > 0) cherries = max(cherries, dp[i][j - 1]);
                    if (i > 0 && j > 0) cherries = max(cherries, dp[i - 1][j - 1]);
                    
                    if (cherries < 0) continue;
                    cherries += grid[i][k - i] + (i == j ? 0 : grid[j][k - j]);
                
                    curr[i][j] = cherries;
                }
            }
            dp = move(curr); 
        }
        
        return 2*max(dp[n-1][n-1], 0); 
}