{leetcode}/problems/minimum-number-of-visited-cells-in-a-grid/[LeetCode - 2617. Minimum Number of Visited Cells in a Grid ^]
You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).
Starting from the cell (i, j), you can move to one of the following cells:
-
Cells
(i, k)withj < k ⇐ grid[i][j] + j(rightward movement), or -
Cells
(k, j)withi < k ⇐ grid[i][j] + i(downward movement).
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.
Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex1.png" style="width: 271px; height: 171px;" />
Input: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]] Output: 4 Explanation: The image above shows one of the paths that visits exactly 4 cells.
Example 2: <img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex2.png" style="width: 271px; height: 171px;" />
Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]] Output: 3 *Explanation: *The image above shows one of the paths that visits exactly 3 cells.
Example 3: <img alt="" src="https://assets.leetcode.com/uploads/2023/01/26/ex3.png" style="width: 181px; height: 81px;" />
Input: grid = [[2,1,0],[1,0,0]] Output: -1 Explanation: It can be proven that no path exists.
Constraints:
-
m == grid.length -
n == grid[i].length -
1 ⇐ m, n ⇐ 105 -
1 ⇐ m * n ⇐ 105 -
0 ⇐ grid[i][j] < m * n -
grid[m - 1][n - 1] == 0