算法第三十天-矩阵中移动的最大次数-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法第三十天-矩阵中移动的最大次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

矩阵中移动的最大次数

题目要求

算法第三十天-矩阵中移动的最大次数,算法基础,算法,python,leetcode

解题思路

网格图 DFS
从第一列的任一单元格 $(i, 0)$ 开始递归。枚举往右上/右/右下三个方向走，如果走一步后，没有出界，且格子值大于 $g r i d [i] [j]$ ，则可以走，继续递归。

在递归过程中，记录能访问到的最大列号，作为答案。

代码实现时，为避免重复递归之前访问过的格子，可以用一个 $v i s$ 数组标记访问过的格子。但实际上，可以把 $g r i d [i] [j]$ 置为 $0$ 从而无需创建 $v i s$ 数组。这是因为网格值均为正数，并且我们只能访问到比当前格子值更大的格子，所以置为 $0$ 会导致永远无法访问到该格子，这正是我们所希望的。

代码

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m,n = len(grid), len(grid[0])
        ans = 0
        def dfs(i,j):
            nonlocal ans
            ans = max(ans,j)
            if ans == n -1:
                return
            for k in i-1, i, i+1:
                if 0<= k <m and grid[k][j+1] >grid[i][j]:
                    dfs(k,j+1)
            grid[i][j] = 0
        for i in range(m):
            dfs(i,0)
        return ans