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

题解：记忆化搜索

这个题可以用深搜去做，从（0，0）点出发，两层for循环记录位置，外层代表四个方向，内层是走了多少步，走到一个位置如果数值比前一步大的话，加上数值继续dfs，每次返回时更新一下最大值。在两层for循环结束后，得到的maxx的值就是该点能得到的最多奶酪数，然后将maxx赋给book[x][y]记录一下这个点的最大奶酪数,这个题有一个剪枝，如果遇到一个点它被记录过了，那么直接用就行了，不用再搜索。最后返回到主函数加上（0，0）点对应的值就好了。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
ll ans,cnt,flag,temp;
ll a[N][N];
int b[][2]={1,0,0,1,-1,0,0,-1};
ll c[N][N];
bool vis[N][N];
char str;
void dfs(int x,int y){
    //printf("%d %d\n",x,y);
    if(c[x][y])
        return;
    c[x][y]=a[x][y];
    for(int i=0;i<4;i++){
        for(int j=1;j<=k;j++){
            int tx=x+b[i][0]*j;
            int ty=y+b[i][1]*j;
            if(tx<1||tx>n||ty<1||ty>n)
                break;
            if(a[x][y]<a[tx][ty]){
                dfs(tx,ty);
                c[x][y]=max(c[x][y],c[tx][ty]+a[x][y]);
            }
        }
    }
}

int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //;
    //scanf("%d",&t);
    while(~scanf("%d%d",&n,&k)){
        if(n==-1&&k==-1)
            break;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%lld",&a[i][j]);
        memset(c,0,sizeof(c));
        dfs(1,1);
        printf("%lld\n",c[1][1]);
    }


    //cout << "Hello world!" << endl;
    return 0;
}