AcWing 901. 滑雪
原题链接
简单
作者:
星星.
,
2023-02-13 21:08:56
,
所有人可见
,
阅读 101
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=310;
int n,m;
int h[N][N];
int f[N][N];
int dp(int i,int j)
{
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
if(f[i][j]!=-1) return f[i][j];
f[i][j]=1;
//初始化f[i][j]=1因为就算不走,这一个点在那也是一步,所以初值为1
for(int x=0;x<4;x++)
{
int a=i+dx[x],b=j+dy[x];
if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[i][j])
f[i][j]=max(f[i][j],dp(a,b)+1);
}
return f[i][j];
}
int main()
{
memset(f,-1,sizeof f);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>h[i][j];
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
res=max(res,dp(i,j));
//我们的dp函数里算的是走的每条路里面的最大值
//然后后来我们还要将这些路再比较一个最大值,就是这个循环的目的
cout<<res;
return 0;
}