AcWing 901. 滑雪
原题链接
简单
作者:
minux
,
2020-05-04 10:58:29
,
所有人可见
,
阅读 520
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int n,m;
int h[N][N];
int f[N][N];
int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int dp(int x, int y){
if(f[x][y]!=-1) return f[x][y];
f[x][y]=1; // 当前路径长度设置为1
for(int *dir: dirs){
int nx=x+dir[0];
int ny=y+dir[1];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && h[nx][ny]<h[x][y])
f[x][y]=max(f[x][y], dp(nx, ny)+1);
}
return f[x][y];
}
int main(){
// 记忆化递归
cin>>n>>m;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
cin>>h[i][j];
memset(f, -1, sizeof f);
int res=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
res=max(res, dp(i, j));
cout<<res<<endl;
return 0;
}