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

#include<iostream>
using namespace std;
int gra[101][101];
int dp[101][101];//表示从i行j列能够获得的最大收益
int n,k;
int dir[4][2]={-1,0,1,0,0,-1,0,1};

int dfs(int i,int j) //记忆法搜索
{
    int s,t,p,q,temp,m=0;
    if(dp[i][j]>0)//走过的就没必要走了
        return dp[i][j];
    for(q=0;q<4;q++)
    {
        for(p=1;p<=k;p++)//一次可以走的步数
        {
            s = i + dir[q][0]*p;
            t = j + dir[q][1]*p;
             if(s>=0 && s<n && t>=0 && t<n && gra[i][j] < gra[s][t])
            {
                temp = dfs(s,t);
                if( m < temp) //从上、下、左、右中找一个最优的
                    m = temp;
            }
        }
    }
    dp[i][j] = m + gra[i][j] ;//本身的值也得加上
    return dp[i][j];
}

int main()
{
    while(cin>>n>>k)
    {
        if(n==-1 && k==-1)
            break;
        int i,j;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                scanf("%d",&gra[i][j]);
                dp[i][j] = 0;
            }
        dfs(0,0);
        cout<<dp[0][0]<<endl;
    }
    return 0;
}