2617. Minimum Number of Visited Cells in a Grid
Hard
50 Points
Array
Dynamic Programming
Stack
Breadth-First Search
Union Find
Heap (Priority Queue)
Matrix
Monotonic Stack
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:
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.
Examples
Example 1
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
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
Input: grid = [[2,1,0],[1,0,0]]
Output: -1
Explanation: It can be proven that no path exists.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0
2617. Minimum Number of Visited Cells in a Grid
Hard
50 Points
Array
Dynamic Programming
Stack
Breadth-First Search
Union Find
Heap (Priority Queue)
Matrix
Monotonic Stack
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:
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.
Examples
Example 1
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
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
Input: grid = [[2,1,0],[1,0,0]]
Output: -1
Explanation: It can be proven that no path exists.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0