3225. Maximum Score From Grid Operations
You are given a 2D matrix grid
of size n x n
. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices (i, j)
, and color black all the cells of the jth
column starting from the top row down to the ith
row.
The grid score is the sum of all grid[i][j]
such that cell (i, j)
is white and it has a horizontally adjacent black cell.
Return the maximum score that can be achieved after some number of operations.
Example 1:
Input: grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
Output: 11
Explanation:
In the first operation, we color all cells in column 1 down to row 3, and in the second operation, we color all cells in column 4 down to the last row. The score of the resulting grid is grid[3][0] + grid[1][2] + grid[3][3]
which is equal to 11.
Example 2:
Input: grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
Output: 94
Explanation:
We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4]
which is equal to 94.
Constraints:
1 <= n == grid.length <= 100
n == grid[i].length
0 <= grid[i][j] <= 109
Solution:
class Solution {
public long maximumScore(int[][] matrix) {
int size = matrix.length;
long[][] columnPrefixSum = new long[size + 1][size];
for (int row = 0; row < size; row++) {
for (int col = 0; col < size; col++) {
columnPrefixSum[row + 1][col] = columnPrefixSum[row][col] + matrix[row][col];
}
}
long[][][] dpTable = new long[size][size + 1][size + 1];
for (long[][] table2D : dpTable)
for (long[] table1D : table2D)
Arrays.fill(table1D, -1);
for (int colored = 0; colored <= size; colored++)
dpTable[0][colored][0] = 0;
for (int currentColumn = 0; currentColumn < size - 1; currentColumn++) {
for (int colored = 0; colored <= size; colored++) {
for (int taken = 0; taken <= size; taken++) {
if (dpTable[currentColumn][colored][taken] == -1)
continue;
for (int newColumn = 0; newColumn <= size; newColumn++) {
if (newColumn > colored) {
long currentValue = dpTable[currentColumn][colored][taken];
if (colored + taken < newColumn) {
currentValue += columnPrefixSum[newColumn][currentColumn] - columnPrefixSum[colored + taken][currentColumn];
}
dpTable[currentColumn + 1][newColumn][0] = Math.max(dpTable[currentColumn + 1][newColumn][0], currentValue);
} else if (newColumn < colored) {
long currentValue = dpTable[currentColumn][colored][taken]
+ columnPrefixSum[colored][currentColumn + 1] - columnPrefixSum[newColumn][currentColumn + 1];
dpTable[currentColumn + 1][newColumn][colored - newColumn] = Math.max(dpTable[currentColumn + 1][newColumn][colored - newColumn], currentValue);
} else {
long currentValue = dpTable[currentColumn][colored][taken];
dpTable[currentColumn + 1][newColumn][0] = Math.max(currentValue, dpTable[currentColumn + 1][newColumn][0]);
}
}
}
}
}
long maxResult = 0;
for (int i = 0; i <= size; i++)
for (int j = 0; j <= size; j++)
maxResult = Math.max(maxResult, dpTable[size - 1][i][j]);
return maxResult;
}
}