2617. Minimum Number of Visited Cells in a Grid Hard

1/**
2 * [2617] Minimum Number of Visited Cells in a Grid
3 *
4 * You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).
5 * Starting from the cell (i, j), you can move to one of the following cells:
6 * 
7 * 	Cells (i, k) with j < k <= grid[i][j] + j (rightward movement), or
8 * 	Cells (k, j) with i < k <= grid[i][j] + i (downward movement).
9 * 
10 * Return the minimum number of cells you need to visit to reach the bottom-right cell (m - 1, n - 1). If there is no valid path, return -1.
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex1.png" style="width: 271px; height: 171px;" />
14 * Input: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
15 * Output: 4
16 * Explanation: The image above shows one of the paths that visits exactly 4 cells.
17 * 
18 * <strong class="example">Example 2:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex2.png" style="width: 271px; height: 171px;" />
20 * Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
21 * Output: 3
22 * Explanation: The image above shows one of the paths that visits exactly 3 cells.
23 * 
24 * <strong class="example">Example 3:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2023/01/26/ex3.png" style="width: 181px; height: 81px;" />
26 * Input: grid = [[2,1,0],[1,0,0]]
27 * Output: -1
28 * Explanation: It can be proven that no path exists.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	m == grid.length
34 * 	n == grid[i].length
35 * 	1 <= m, n <= 10^5
36 * 	1 <= m * n <= 10^5
37 * 	0 <= grid[i][j] < m * n
38 * 	grid[m - 1][n - 1] == 0
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid/
44// discuss: https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn minimum_visited_cells(grid: Vec<Vec<i32>>) -> i32 {
50        0
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_2617() {
62    }
63}
64