3256. Maximum Value Sum by Placing Three Rooks I Hard

1/**
2 * [3256] Maximum Value Sum by Placing Three Rooks I
3 *
4 * You are given a m x n 2D array board representing a chessboard, where board[i][j] represents the value of the cell (i, j).
5 * Rooks in the same row or column attack each other. You need to place three rooks on the chessboard such that the rooks do not attack each other.
6 * Return the maximum sum of the cell values on which the rooks are placed.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">board = </span>[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
11 * Output: 4
12 * Explanation:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" />
14 * We can place the rooks in the cells (0, 2), (1, 3), and (2, 1) for a sum of 1 + 1 + 2 = 4.
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span>
19 * Output: <span class="example-io">15</span>
20 * Explanation:
21 * We can place the rooks in the cells (0, 0), (1, 1), and (2, 2) for a sum of 1 + 5 + 9 = 15.
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">board = [[1,1,1],[1,1,1],[1,1,1]]</span>
26 * Output: <span class="example-io">3</span>
27 * Explanation:
28 * We can place the rooks in the cells (0, 2), (1, 1), and (2, 0) for a sum of 1 + 1 + 1 = 3.
29 * </div>
30 *  
31 * Constraints:
32 * 
33 * 	3 <= m == board.length <= 100
34 * 	3 <= n == board[i].length <= 100
35 * 	-10^9 <= board[i][j] <= 10^9
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-i/
41// discuss: https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-i/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn maximum_value_sum(board: Vec<Vec<i32>>) -> i64 {
47        
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_3256() {
59    }
60}
61