You are given a 0-indexed
m x n integer matrix
grid. Your initial position is at the top-left cell
Starting from the cell
(i, j), you can move to one of the following cells:
j < k <= grid[i][j] + j(rightward movement), or
i < 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
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.
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.
Input: grid = [[2,1,0],[1,0,0]] Output: -1 Explanation: It can be proven that no path exists.
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