AcWing 901. 滑雪-python
原题链接
简单
作者:
Actor丶
,
2020-02-05 19:14:11
,
所有人可见
,
阅读 506
# 1.输入示例
r,c = map(int, input().split())
arr = [[0 for i in range(c+1)] for j in range(r+1)]
for i in range(1, r+1):
in_li = list(map(int, input().split()))
for j in range(1, c+1):
arr[i][j] = in_li[j-1]
# 2. 初始化dp数组
dp = [[-1 for i in range(c+1)] for j in range(r+1)]
# 3.递归搜索
dx = [-1,0,1,0] # !!!技巧:遍历方格的上下左右四个方向的技巧,新建两个这样的数组
dy = [0,1,0,-1]
def dfs(i,j):
if dp[i][j]!=-1:
return dp[i][j]
dp[i][j] = 1 # 初始化dp[i][j]等于1,表示路劲只包含[i,j]元素,长度为1
for d in range(4):
a = i+dx[d]
b = j+dy[d]
if a>=1 and a<=r and b>=1 and b<=c and arr[a][b]<arr[i][j]: # !出错,最后要比较arr数组中移动一个位置前后的高度大小
dp[i][j] = max(dp[i][j], dfs(a,b)+1)
return dp[i][j]
res = 0
for i in range(1, r+1):
for j in range(1, c+1):
res = max(res, dfs(i,j))
print(res)