摸鱼小渣 @ 2021-10-12 17:06:02
用的是记忆化搜索 1.f数组存放以某个点作为起点能滑行的最远距离。 2.a数组存放每个点的高度。
#include<iostream>
#include<cmath>
using namespace std;
int a[201][201],f[201][201],n,k,maxn=1;
int dfs(int x,int y)
{
f[x][y]=1;
if((x-1>=1)&&(a[x-1][y]>a[x][y]))
{
f[x-1][y]=max(f[x-1][y],f[x][y]+1);
dfs(x-1,y);
}
if((x+1<=n)&&(a[x+1][y]>a[x][y]))
{
f[x+1][y]=max(f[x+1][y],f[x][y]+1);
dfs(x+1,y);
}
if((y-1>=1)&&(a[x][y-1]>a[x][y]))
{
f[x][y-1]=max(f[x][y-1],f[x][y]+1);
dfs(x,y-1);
}
if((y+1<=k)&&(a[x][y+1]>a[x][y]))
{
f[x][y+1]=max(f[x][y+1],f[x][y]+1);
dfs(x,y+1);
}
return f[x][y];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
cin>>a[i][j];
f[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
maxn=max(maxn,dfs(i,j));
cout<<maxn;
}