2684.矩阵中移动的最大次数

链接：2684.矩阵中移动的最大次数
难度：Medium
标签：数组、动态规划、矩阵
简介：返回你在矩阵中能够 移动 的 最大 次数。

题解 1 - python

• 编辑时间：2024-03-16
• 执行用时：226ms
• 内存消耗：41.75MB
• 编程语言：python
• 解法介绍：dfs。

dirs = [(1, 1), (0, 1), (-1, 1)]
    class Solution:
        def maxMoves(self, grid: List[List[int]]) -> int:
            n, m = len(grid), len(grid[0])
            @cache
            def dfs(row: int, col: int) -> int:
                ans = 0
                for x, y in dirs:
                    nrow, ncol = row + x, col + y
                    if 0 <= nrow < n and 0 <= ncol < m and grid[row][col] < grid[nrow][ncol]:
                        ans = max(ans, 1 + dfs(nrow, ncol))
                return ans
            return max(dfs(row, 0) for row in range(n))