You are given a $0$ indexed $m \times n$ integer matrix grid. Your starting position is at the cell $(0, 0)$.

When you are located at cell $(i, j)$, you can move to any of the following cells:

• Cell $(i, k)$ such that $j < k \leq \min(j + {`grid`}[i][j], n - 1)$ (moving to the right in the same row).

• Cell $(k, j)$ such that $i < k \leq \min(i + {`grid`}[i][j], m - 1)$ (moving downward in the same column).

Return the minimum number of cells you need to visit to reach the cell $(m - 1, n - 1)$. If the cell $(m - 1, n - 1)$ cannot be reached, return $-1$.

Constraints:

• m $==$ grid.length

• n $==$ grid[i].length

• $1 \leq$ m, n $\leq 10^5$

• $1 \leq$ m $ imes$ n $\leq 10^5$

• $0 \leq$ grid[i][j] $<$ m $\times$ n

• grid[m - 1][n - 1] $== 0$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.