pku1088滑雪（记忆性搜索）

368K

0MS

GCC

817B

2009-01-12 18:56:19

best[i][j]存放从i，j开始点处开始走的最长距离。

对于给定点i，j都深搜其周围的符合条件的点

即dp(i+1,j),dp(i-1,j),dp(i,j+1),dp(i,j-1)

我的程序对于最长距离为1的起点，没有记忆性。不过最长距离为1，那么其周围四个点都要比它大，只要四次判断就可以，不会占用太多时间。

代码如下：

 

#include<stdio.h>
int r,c,num[102][102],best[102][102];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void input()
{
    int i,j;
    scanf("%d %d",&r,&c);
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
            scanf("%d",&num[i][j]);
}
void init()
{
    int i,j;
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
            best[i][j]=1;

}
int test(int i,int j)
{
    return i>=1&&i<=r&&j>=1&&j<=c;
}
int dp(int i,int j)
{
    int k,a,b;
    if(best[i][j]>1)    return best[i][j];
    for(k = 0; k < 4; k ++){
        if(test(i+dx[k],j+dy[k])){
            a=i+dx[k];b=j+dy[k];
            if(num[a][b]<num[i][j]&&dp(a,b)+1>best[i][j])
                best[i][j]=dp(a,b)+1;
        
        }
    }
        
    return best[i][j];
}
int main()
{
    int max=-999999,i,j;
    input();
    init();
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
            if(dp(i,j)>max)
                max=dp(i,j);
    printf("%d\n",max);
}