1594. Maximum Non Negative Product in a Matrix Medium

1/**
2 * [1594] Maximum Non Negative Product in a Matrix
3 *
4 * You are given a m x n matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.
5 * Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (m - 1, n - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.
6 * Return the maximum non-negative product modulo 10^9 + 7. If the maximum product is negative, return -1.
7 * Notice that the modulo is performed after getting the maximum product.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/23/product1.jpg" style="width: 244px; height: 245px;" />
11 * Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
12 * Output: -1
13 * Explanation: It is not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/23/product2.jpg" style="width: 244px; height: 245px;" />
17 * Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
18 * Output: 8
19 * Explanation: Maximum non-negative product is shown (1 * 1 * -2 * -4 * 1 = 8).
20 * 
21 * Example 3:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/23/product3.jpg" style="width: 164px; height: 165px;" />
23 * Input: grid = [[1,3],[0,-4]]
24 * Output: 0
25 * Explanation: Maximum non-negative product is shown (1 * 0 * -4 = 0).
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	m == grid.length
31 * 	n == grid[i].length
32 * 	1 <= m, n <= 15
33 * 	-4 <= grid[i][j] <= 4
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
39// discuss: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_1594() {
57    }
58}
59