# Untitled

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);
}```