poj 1088 滑雪

//滑雪，记忆化搜索解决
//dp[i][j]表示从（i，j）开始出发所能滑的最长长度
//显然状态转移方程为dp[i][j]=max{上下左右四个方向的dp值}+1;
//我们只需要在DP过程中时刻更新最大值MAX即可
#include <stdio.h>
#include <string.h>
#define N 110
int R,C;
int a[N][N],dp[N][N],MAX;
bool vis[N][N];
int x[5]={0,-1,1,0,0}, y[5]={0,0,0,-1,1};

void DP(int i , int j)
{
    int k,xx,yy,tmp;
    if(vis[i][j]) return ;
    vis[i][j]=1;
    dp[i][j]=1;
    for(k=1; k<=4; k++)  //枚举四个方向
    {
        xx=i+x[k];  yy=j+y[k];  //得到新的坐标
        if( xx>=1 && xx<=R && yy>=1 && yy<=C && a[xx][yy]>a[i][j] )
        {
            DP(xx,yy);
            if(dp[xx][yy]+1 > dp[i][j])
                dp[i][j]=dp[xx][yy]+1;
        }
    }
    return  ;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&R,&C)!=EOF)
    {
        for(i=1; i<=R; i++)
            for(j=1; j<=C; j++)
                scanf("%d",&a[i][j]);
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        MAX=-1;
        for(i=1; i<=R; i++)
            for(j=1; j<=C; j++)
                if(!vis[i][j])
                {
                    DP(i,j);
                    MAX=MAX>dp[i][j]?MAX:dp[i][j];
                }
        printf("%d\n",MAX);
    }
    return 0;
}