Untitled
unknown
plain_text
3 years ago
1.6 kB
4
Indexable
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); }
Editor is loading...