题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1078

题目大意：

题目中的k表示横向或者竖直最多可曾经进的距离，不可以拐弯。老鼠的出发点是(1,1)。

对于老鼠从当前点可以到达的点。筛选出从这些点到达当前点所能获得的cheese的最大值。

思路：记忆化搜索。

假设对于当前的点。没有被搜索过（dp[i][j]=0）。那么就对其进行搜索。搜索过程中记录下最优的解。

假设已经被搜索过了，就能够直接利用已经记录的值来进行推断 了，不须要再去搜索。

假设搜索完以后结果还是0。表明他不能再有新的路能够走了。结果就是他本身了。

#include<stdio.h>

#include<string.h>

#define LL __int64

#define max(a,b) a>b?

a:b

int n,k;

LL a[105][105],dp[105][105];

int dir[][2]={0,1,0,-1,1,0,-1,0};

void dfs(int x,int y)

{

    for(int i=0;i<4;i++)

    {

        for(int j=1;j<=k;j++)

        {

        int xx=x+dir[i][0]*j;

        int yy=y+dir[i][1]*j;

            if(xx<=0||yy<=0||xx>n||yy>n)continue;

            if(a[xx][yy]>a[x][y]){

                if(dp[xx][yy]==0){     //假设没有被搜索过

                    dfs(xx,yy);

                    dp[x][y]=max(dp[xx][yy]+a[x][y],dp[x][y]);

                }

                else dp[x][y]=max(dp[xx][yy]+a[x][y],dp[x][y]);

            }

    }

}

if(dp[x][y]==0)dp[x][y]=a[x][y];    //表明已经没有路能够走了。

return ;

}

int main()

{

    int i,j;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        if(n==-1&&k==-1)break;

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        scanf("%I64d",&a[i][j]);

        memset(dp,0,sizeof(dp));

      dfs(1,1);

        printf("%I64d\n",dp[1][1]);

    }

    return 0;

}