2684. Maximum Number of Moves in a Grid
给一个n*m的二维矩阵里面都是正整数
从第一行任一个元素开始
满足下列条件(row,col)可以往(row-1,col+1)、(row,col+1)、(row-1,col+1)移动
你要目标cell的值比现在cell的值还大
请问最多可以做几次移动?
思路:
就照着题目做
用两个长度为n的dp矩阵
dp1纪录matrix[i][j]有没有路径可以抵达
dp2纪录matrix[i][j+1]有没有路径可以抵达
从第一行开始一直到第m-1行
如果dp1[i] == j表示matrix[i][j]有路径可以抵达
接着去检查三个方向的值有没有比matrix[i][j]大
有的话对应方向的dp2=dp[i]+1
然后把dp1=dp2并建立一个新的dp2，继续下一轮
最后把dp1最大的值回传就好
golang code :
func maxMoves(grid [][]int) int {
n, m := len(grid), len(grid[0])
tmp1 := make([][]int, 1)
tmp1[0] = make([]int, m)
tmp2 := make([][]int, 1)
tmp2[0] = make([]int, m)
grid = append(tmp1, grid...)
grid = append(grid, tmp2...)
ans := 0
dp1 := make([]int, n+2)
dp2 := make([]int, n+2)
for j := 0; j < m-1; j++ {
for i := 1; i <= n; i++ {
if dp1[i] == j {
if grid[i][j] < grid[i-1][j+1] {
dp2[i-1] = j + 1
ans = max(dp2[i-1], ans)
}
if grid[i][j] < grid[i][j+1] {
dp2[i] = j + 1
ans = max(dp2[i], ans)
}
if grid[i][j] < grid[i+1][j+1] {
dp2[i+1] = j + 1
ans = max(dp2[i+1], ans)
}
}
}
dp1 = dp2
dp2 = make([]int, n+2)
}
return ans
}