<p>You are given a <strong>0-indexed</strong> <code>m x n</code> integer matrix <code>grid</code>. Your initial position is at the <strong>top-left</strong> cell <code>(0, 0)</code>.</p>

<p>Starting from the cell <code>(i, j)</code>, you can move to one of the following cells:</p>

<ul>
	<li>Cells <code>(i, k)</code> with <code>j &lt; k &lt;= grid[i][j] + j</code> (rightward movement), or</li>
	<li>Cells <code>(k, j)</code> with <code>i &lt; k &lt;= grid[i][j] + i</code> (downward movement).</li>
</ul>

<p>Return <em>the minimum number of cells you need to visit to reach the <strong>bottom-right</strong> cell</em> <code>(m - 1, n - 1)</code>. If there is no valid path, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex1.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The image above shows one of the paths that visits exactly 4 cells.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex2.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>The image above shows one of the paths that visits exactly 3 cells.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/26/ex3.png" style="width: 181px; height: 81px;" />
<pre>
<strong>Input:</strong> grid = [[2,1,0],[1,0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be proven that no path exists.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= grid[i][j] &lt; m * n</code></li>
	<li><code>grid[m - 1][n - 1] == 0</code></li>
</ul>

# Solution 2: monotonic stack solution

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        colq = [[] for _ in range(cols)] # (row, path length), path length is min number of steps from the current grid to the end
        # It is more convenient if you traverse in reversed order, because we only need to consider grid[r][c] of the current
        # elements. Otherwise we need to consider grid[r][c] for all the visited elements.
        for r in range(rows - 1, -1, -1):
            rowq = [] # (column, path length), path length is min number of steps from the current grid to the end
            for c in range(cols - 1, -1, -1):
                if r == rows - 1 and c == cols - 1:
                    rowq.append((c, 1))
                    colq[c].append((r, 1))
                else:
                    delta = grid[r][c]
                    path_len = float("inf")
                    # Consider DP array: [?, ?, x, y, z]
                    # We have x > y > z based on the monotonicity property
                    # For the second ?, if x, y and z make range constraint hold, we pop up x and y and leave z.
                    # So the result is [?, z + 1, z]
                    # For the first ?, the popped element x and y will not be used.
                    # If x is in the range, then either for z + 1, and z + 1 <= x (x > z), so z + 1 is more optimal than x.
                    # Thus it is safe to pop up x and y.
                    while len(rowq) > 1 and rowq[-2][0] - delta <= c:
                        # rowq[-1] can be discarded
                        rowq.pop()
                    path_len = min(path_len, rowq[-1][1] + 1 if rowq and rowq[-1][0] - delta <= c else float("inf"))
                    while len(colq[c]) > 1 and colq[c][-2][0] - delta <= r:
                        colq[c].pop()
                    path_len = min(path_len, colq[c][-1][1] + 1 if colq[c] and colq[c][-1][0] - delta <= r else float("inf"))
                    # Prepare to update the stack
                    # We need to maintain the monotonicity of the stack, i.e., the path length is monotonically increasing
                    # For example: [x,4,1,1,1]
                    # DP[1] = 2, DP[2] = 3.
                    # If 2 is in the range of x, then it must be the same for 1.
                    # Since DP[1] < DP[2], 1 is always more optimal than 2.
                    # So we need to discard 2. That is how monotonic stack works.
                    while rowq and rowq[-1][1] >= path_len:
                        rowq.pop()
                    rowq.append((c, path_len))
                    while colq[c] and colq[c][-1][1] >= path_len:
                        colq[c].pop()
                    colq[c].append((r, path_len))
            if r == 0:
                ans = rowq[-1][1]
                return ans if ans < float("inf") else -1
        return -1
51800