矩阵中移动的最大次数
题目要求
解题思路
网格图 DFS 从第一列的任一单元格
(
i
,
0
)
(i,0)
(i,0) 开始递归。枚举往右上/右/右下三个方向走，如果走一步后，没有出界，且格子值大于
g
r
i
d
[
i
]
[
j
]
grid[i][j]
grid[i][j]，则可以走，继续递归。
在递归过程中，记录能访问到的最大列号，作为答案。
代码实现时，为避免重复递归之前访问过的格子，可以用一个
v
i
s
vis
vis数组标记访问过的格子。但实际上，可以把
g
r
i
d
[
i
]
[
j
]
grid[i][j]
grid[i][j]置为
0
0
0从而无需创建
v
i
s
vis
vis数组。这是因为网格值均为正数，并且我们只能访问到比当前格子值更大的格子，所以置为
0
0
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
dfs(k,j+1)
grid[i][j] = 0
for i in range(m):
dfs(i,0)
return ans
复杂度分析
时间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中
m
m
m 和
n
n
n 分别为
g
r
i
d
grid
grid 的行数和列数。每个格子至多递归一次。空间复杂度：
O
(
n
)
O(n)
O(n)。递归需要
O
(
n
)
O(n)
O(n)的栈空间。
参考
灵茶山艾府
文章链接
发表评论