# https://leetcode.com/problems/maximum-number-of-moves-in-a-grid
from typing import List

DIRS =  [[-1, 1], [0, 1], [1, 1]]
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        memo = [[-1] * len(l) for l in grid]
        def recurse(y, x, curr: int) -> int:
            ret = curr
            if memo[y][x] != -1:
                return memo[y][x]
            for [new_y, new_x] in DIRS:
                new_y += y
                new_x += x
                if new_y >= len(grid) or \
                    new_y < 0 or \
                    new_x >= len(grid[0]) or \
                    new_x < 0 or \
                    grid[new_y][new_x] <= grid[y][x]:
                    continue
                ret = max(ret, recurse(new_y, new_x, curr + 1))
            memo[y][x] = ret
            return ret
        ret = 0
        for y in range(len(grid)):
            ret = max(ret, recurse(y, 0, 0))
        return ret