StaffArrayBreadth-First SearchDynamic ProgrammingHeap (Priority Queue)MatrixMonotonic StackStackUnion-Find
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] + jfor rightward movement. - Cells
(k, j)withi < k <= grid[i][j] + ifor 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
3 4 2 1 4 2 3 1 2 1 0 0 2 4 0 0
Input
grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]Output
4The image above shows one of the paths that visits exactly 4 cells.
Example 2
3 4 2 1 4 2 1 1 2 1 1 0 3 4 1 0
Input
grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]Output
3The image above shows one of the paths that visits exactly 3 cells.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10^5
- 1 <= m * n <= 10^5
- 0 <= grid[i][j] < m * n
- grid[m - 1][n - 1] == 0