#2617
Minimum Number of Visited Cells in a Grid
international master · 2130 · lc hard +32 · verified · 23.6% accepted · 416 likes · top 3%
Description
You are given a 0-indexed m x n integer matrix grid. Starting at (0, 0), from cell (i, j) you may move right to (i, k) for j < k <= j + grid[i][j], or down to (k, j) for i < k <= i + grid[i][j]. Return the minimum number of cells visited to reach (m - 1, n - 1), or -1 if unreachable.
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.
Code
1
2
3