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

矩阵中移动的最大次数

题目要求

解题思路

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

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

代码实现时，为避免重复递归之前访问过的格子，可以用一个 $vis$数组标记访问过的格子。但实际上，可以把 $grid[i][j]$置为$0$从而无需创建$vis$数组。这是因为网格值均为正数，并且我们只能访问到比当前格子值更大的格子，所以置为 $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

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别为 $grid$ 的行数和列数。每个格子至多递归一次。
• 空间复杂度：$O(n)$。递归需要 $O(n)$的栈空间。

参考

灵茶山艾府