1463. Cherry Pickup II Hard

1/**
2 * [1463] Cherry Pickup II
3 *
4 * You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.
5 * You have two robots that can collect cherries for you:
6 * 
7 * 	Robot #1 is located at the top-left corner (0, 0), and
8 * 	Robot #2 is located at the top-right corner (0, cols - 1).
9 * 
10 * Return the maximum number of cherries collection using both robots by following the rules below:
11 * 
12 * 	From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
13 * 	When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
14 * 	When both robots stay in the same cell, only one takes the cherries.
15 * 	Both robots cannot move outside of the grid at any moment.
16 * 	Both robots should reach the bottom row in grid.
17 * 
18 *  
19 * Example 1:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1802.png" style="width: 374px; height: 501px;" />
21 * Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
22 * Output: 24
23 * Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
24 * Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
25 * Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
26 * Total of cherries: 12 + 12 = 24.
27 * 
28 * Example 2:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/sample_2_1802.png" style="width: 500px; height: 452px;" />
30 * Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
31 * Output: 28
32 * Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
33 * Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
34 * Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
35 * Total of cherries: 17 + 11 = 28.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	rows == grid.length
41 * 	cols == grid[i].length
42 * 	2 <= rows, cols <= 70
43 * 	0 <= grid[i][j] <= 100
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/cherry-pickup-ii/
49// discuss: https://leetcode.com/problems/cherry-pickup-ii/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1463() {
67    }
68}
69