poj-1088-滑雪-记忆化搜索

poj-1088-滑雪
考察点 记忆化搜索

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring> 
using namespace std;
int dp[101][101];
int n,m;
int value[101][101]; 
int dfs(int x,int y)
{
    if(dp[x][y]!=-1)
{
    return dp[x][y];
}
int a=1,b=1,c=1,d=1;
if((x-1)>=0)
{
    if(value[x][y]>value[x-1][y])
    {
        a=dfs(x-1,y)+1;
    }
}
if((x+1)<n)
{
    if(value[x][y]>value[x+1][y])
    {
        b=dfs(x+1,y)+1;
    }
}
if((y-1)>=0)
{
    if(value[x][y]>value[x][y-1])
    {
        c=dfs(x,y-1)+1;
    }
}
if((y+1)<m)
{
    if(value[x][y]>value[x][y+1])
    {
        d=dfs(x,y+1)+1;
    }
}
int t=max(a,b);
t=max(t,c);
t=max(t,d);
dp[x][y]=t;
return t;//返回的是以i,j为开始最长的数字 
}
int main()
{
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    cin>>value[i][j];
    int ma=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            ma=max(ma,dfs(i,j));
        }
    } 
    cout<<ma;
    return 0;
}