AcWing 901. 滑雪
原题链接
简单
作者:
sy123
,
2020-12-24 15:53:18
,
所有人可见
,
阅读 277
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n, m;
int g[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//dp[i][j]表示从这个点出发达到的最大距离
int dp(int x, int y)
{
int &v=f[x][y];//注意这里是引用,v代表f[x][y]
if(v!=-1)return v;//已经被计算过
v = 1;//最少有一个距离长度
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&g[a][b]<g[x][y]){
v=max(v,dp(a,b)+1);
}
}
return v;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &g[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));
printf("%d\n", res);
return 0;
}