<p>You are given a <strong>0-indexed</strong> <code>m x n</code> matrix <code>grid</code> consisting of <strong>positive</strong> integers.</p>

<p>You can start at <strong>any</strong> cell in the first column of the matrix, and traverse the grid in the following way:</p>

<ul>
	<li>From a cell <code>(row, col)</code>, you can move to any of the cells: <code>(row - 1, col + 1)</code>, <code>(row, col + 1)</code> and <code>(row + 1, col + 1)</code> such that the value of the cell you move to, should be <strong>strictly</strong> bigger than the value of the current cell.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of <strong>moves</strong> that you can perform.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png" style="width: 201px; height: 201px;" />
<pre>
<strong>Input:</strong> grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can start at the cell (0, 0) and make the following moves:
- (0, 0) -&gt; (0, 1).
- (0, 1) -&gt; (1, 2).
- (1, 2) -&gt; (2, 3).
It can be shown that it is the maximum number of moves that can be made.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png" />
<strong>Input:</strong> grid = [[3,2,4],[2,1,9],[1,1,7]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> Starting from any cell in the first column we cannot perform any moves.
</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>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        #self.grid = grid
        #self.dp = {}
        return self.base_try(grid)

    def check_next_moves(self, x, y):
        next_moves = [(x-1, y+1), (x, y+1), (x+1,y+1)]
        ret = []
        for move in next_moves:
            if self.is_valid_move(move[0], move[1]):
                ret.append(move)
        return ret

    def is_valid_move(self, x1, y1, grid):
        if (0 <= x1 < len(self.grid)) and (0 <= y1 < len(self.grid[0])) and self.grid[x][y] < self.grid[x1][y1]:
            return True
        else:
            return False

    def base_try(self, grid):
        #TLE on case 810/814. hint suggests dp. note that we can move diagonal left and up diagonal down and right, and 
        #right. We cannot move left, so calculating each spot row 0 to n left to right will work
        starters = [(i, 0) for i in range(len(grid))]
        max_moves = 0
        seen = set()
        for start in starters:
            stack = [(start[0], start[1], 0)]
            while stack:
                x, y, move_count = stack.pop()
                next_moves = [(x-1, y+1), (x, y+1), (x+1,y+1)]
                for x1,y1 in next_moves:
                    if (0 <= x1 < len(grid)) and (0 <= y1 < len(grid[0])) and grid[x][y] < grid[x1][y1]:
                        if (x1,y1) not in seen:
                            max_moves = max(max_moves, move_count + 1)
                            stack.append((x1,y1,move_count+1))
                            seen.add((x1,y1))
        return max_moves
984