Skip to content

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:

img

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:

img

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