{"date":"2026-04-29","link":"/problems/maximum-score-from-grid-operations/","question":{"questionId":"3470","questionFrontendId":"3225","title":"Maximum Score From Grid Operations","titleSlug":"maximum-score-from-grid-operations","translatedTitle":null,"difficulty":"Hard","acRate":51.38327261080193,"topicTags":[{"name":"Array","slug":"array","nameTranslated":null},{"name":"Dynamic Programming","slug":"dynamic-programming","nameTranslated":null},{"name":"Matrix","slug":"matrix","nameTranslated":null},{"name":"Prefix Sum","slug":"prefix-sum","nameTranslated":null}],"content":"<p>You are given a 2D matrix <code>grid</code> of size <code>n x n</code>. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices <code>(i, j)</code>, and color black all the cells of the <code>j<sup>th</sup></code> column starting from the top row down to the <code>i<sup>th</sup></code> row.</p>\n\n<p>The grid score is the sum of all <code>grid[i][j]</code> such that cell <code>(i, j)</code> is white and it has a horizontally adjacent black cell.</p>\n\n<p>Return the <strong>maximum</strong> score that can be achieved after some number of operations.</p>\n\n<p>&nbsp;</p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">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]]</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">11</span></p>\n\n<p><strong>Explanation:</strong></p>\n<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2024/05/11/one.png\" style=\"width: 300px; height: 200px;\" />\n<p>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 <code>grid[3][0] + grid[1][2] + grid[3][3]</code> which is equal to 11.</p>\n</div>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">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]]</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">94</span></p>\n\n<p><strong>Explanation:</strong></p>\n<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2024/05/11/two-1.png\" style=\"width: 300px; height: 200px;\" />\n<p>We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is <code>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]</code> which is equal to 94.</p>\n</div>\n\n<p>&nbsp;</p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>1 &lt;=&nbsp;n == grid.length &lt;= 100</code></li>\n\t<li><code>n == grid[i].length</code></li>\n\t<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>\n</ul>\n"}}