board with m rows and n columns filled with non-negative integers. You stand in the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).
From the cell (i, j) holding v = board[i][j] a single move can take you:
- right along the same row to any cell (i, k) with j < k ≤ j + v;
- down the same column to any cell (k, j) with i < k ≤ i + v.
Return the smallest number of cells you have to visit on the way, counting both the start and the finish. If the finish cannot be reached, return -1.board=[[1, 3, 2], [0, 0, 0], [0, 0, 0]] → 4
The route (0, 0) → (0, 1) → (0, 2) → (2, 2): the value 2 at (0, 2) lets you drop two rows at once. That is 4 cells, counting both the start and the finish.
board=[[4, 0, 0, 0, 0]] → 2
From the start you can leap straight to the last cell, so 2 cells are visited.
board=[[2, 0, 0], [0, 0, 0], [0, 0, 0]] → -1
Only cells holding 0 are reachable from the start, and there is nowhere to go from them.
m, nm · n ≤ 10⁵board[i][j] < m · nboard[m - 1][n - 1] = 0board=[[1, 3, 2], [0, 0, 0], [0, 0, 0]]
4
Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.