Score a Grid After Coloring Column Prefixes

# Score a Grid After Coloring Column Prefixes ### Problem You are given an `n x n` integer matrix `grid`. Every cell is initially white. In one operation, choose a cell `(i, j)` and color column `j` black from row `0` through row `i`, inclusive. You may perform any number of operations, including zero. The score is the sum of the values of white cells that have at least one horizontally adjacent black cell. Horizontal adjacency means the cell immediately to the left or right in the same row. Count a qualifying white cell once, even if both neighbors are black. Return the maximum possible score. You only return the score, not the operations or final coloring. ### C++ Interface ```cpp class Solution { public: long long maximumScore(vector<vector<int>>& grid); }; ``` ### Examples #### Example 1 **Input:** `grid = [[2,7],[5,1]]` **Output:** `8` **Explanation:** Color both cells in column `0` black and leave column `1` white. Both white cells qualify, giving `7 + 1 = 8`. Coloring column `1` completely instead gives `2 + 5 = 7`; stopping either black prefix earlier cannot improve on `8`. #### Example 2 **Input:** `grid = [[0,4,0],[0,9,0],[0,2,0]]` **Output:** `15` **Explanation:** Color columns `0` and `2` completely black and leave column `1` white. Its values contribute `4 + 9 + 2 = 15`, each once despite having two black neighbors. These are all the nonzero values in the grid, so a larger score is impossible. ### Constraints - `1 <= n == grid.size() <= 100` - `grid[i].size() == n` - `0 <= grid[i][j] <= 10^9` - All indices are zero-based. ### Clarifying Questions - Can an operation color an isolated lower cell? No. It always colors every cell above it in the same column too. - Do vertical black neighbors contribute? No. Only left and right neighbors matter. - Can a black cell contribute its own value? No. Only white cells can contribute. ### What a Strong Answer Covers - An exact account of eligible white cells, including boundaries and cells with two black neighbors. - Why the considered final colorings cover every result obtainable by the allowed operations. - A correctness argument for the maximum score, with time and space bounds suitable for `n <= 100`. - Safe handling of large sums and the single-column case. ### Follow-up Questions - What is the answer when `n = 1`, and why? - How would your representation and complexity change for a rectangular grid with `r` rows and `c` columns? ```hint Describe a final coloring After all operations, each column consists of a black prefix followed by a white suffix. Include a prefix of length zero among the possibilities. ``` ```hint Finish one column's score Once the black-prefix lengths of a column and its two neighbors are known, its contribution is fixed. A column prefix sum can evaluate that contribution without scanning its cells again. ```