3225. Maximum Score From Grid Operations Hard

1/**
2 * [3225] Maximum Score From Grid Operations
3 *
4 * 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 j^th column starting from the top row down to the i^th row.
5 * 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.
6 * Return the maximum score that can be achieved after some number of operations.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <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>
11 * Output: <span class="example-io">11</span>
12 * Explanation:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/one.png" style="width: 300px; height: 200px;" />
14 * 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.
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <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>
19 * Output: <span class="example-io">94</span>
20 * Explanation:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/two-1.png" style="width: 300px; height: 200px;" />
22 * 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.
23 * </div>
24 *  
25 * Constraints:
26 * 
27 * 	1 <= n == grid.length <= 100
28 * 	n == grid[i].length
29 * 	0 <= grid[i][j] <= 10^9
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/maximum-score-from-grid-operations/
35// discuss: https://leetcode.com/problems/maximum-score-from-grid-operations/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn maximum_score(grid: Vec<Vec<i32>>) -> i64 {
41        
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_3225() {
53    }
54}
55