741. Cherry Pickup Hard

1/**
2 * [741] Cherry Pickup
3 *
4 * You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
5 * 
6 * 	0 means the cell is empty, so you can pass through,
7 * 	1 means the cell contains a cherry that you can pick up and pass through, or
8 * 	-1 means the cell contains a thorn that blocks your way.
9 * 
10 * Return the maximum number of cherries you can collect by following the rules below:
11 * 
12 * 	Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
13 * 	After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
14 * 	When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
15 * 	If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.
16 * 
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/14/grid.jpg" style="width: 242px; height: 242px;" />
20 * Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
21 * Output: 5
22 * Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
23 * 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
24 * Then, the player went left, up, up, left to return home, picking up one more cherry.
25 * The total number of cherries picked up is 5, and this is the maximum possible.
26 * 
27 * Example 2:
28 * 
29 * Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
30 * Output: 0
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	n == grid.length
36 * 	n == grid[i].length
37 * 	1 <= n <= 50
38 * 	grid[i][j] is -1, 0, or 1.
39 * 	grid[0][0] != -1
40 * 	grid[n - 1][n - 1] != -1
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/cherry-pickup/
46// discuss: https://leetcode.com/problems/cherry-pickup/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
52        0
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_741() {
64    }
65}
66