哭了,为啥会wa两个点

P1434 [SHOI2002] 滑雪

摸鱼小渣 @ 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;
}

|