Description
You are given a 0-indexed m x n integer matrix grid. You start at (0, 0) and want to reach (m-1, n-1). From (i, j) you can move to any cell in the same row with column in [j+1, j+grid[i][j]] or same column with row in [i+1, i+grid[i][j]]. Return minimum cells to visit, or -1.
Examples
Input:
grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]Output:
4Explanation:
Path: (0,0) -> (0,2) -> (0,3) -> (1,3) -> (3,3)
Input:
grid = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
grid = [[2,1,1],[1,2,0],[0,0,1]]Output:
-1Explanation:
Starting at (0,0) with value 2, reachable cells include (0,1), (0,2), (1,0), (2,0). From (0,2) with value 1, cells (0,3) and (1,2) are reachable. The shortest path to (2,3) visits 4 cells total.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 ≤ m, n ≤ 10^5