记搜,始终wa第二个点

P1434 [SHOI2002] 滑雪

xueat @ 2021-03-05 09:40:11

第二个点数据貌似是9900,然而我的输出是9801,晕了晕了。 以下是代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int arr[105][105];
int rec[105][105];
int row,col;
int dp(int row,int col)
{
    if(rec[row][col])
    {
        return rec[row][col];
    }
    int maxn=0;
    bool flag=false;
    for(int i=0;i<4;i++)
    {
        int rr=row+dx[i],cc=col+dy[i];
        if(rr>=0&&cc>=0&&cc<::col&&rr<::row)
        if(arr[rr][cc]<arr[row][col])
        {
            maxn=max(maxn,dp(rr,cc));
            flag=true;//flag判断是否到达搜索终点
        }

    }
    if(flag==false)//如果为终点
        {
            rec[row][col]=1;
            return rec[row][col];
        }
    rec[row][col]=maxn+1;
    return maxn+1;
}
int main()
{
    cin>>row>>col;
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            cin>>arr[i][j];
        }
    }
    int ans=-1;

    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            ans=max(ans,dp(j,i));
        }
    }
    cout<<ans;
    system("pause");
    return 0;
}

|