http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1107

 

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he's going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input Specification

There are several test cases. Each test case consists of

• a line containing two integers between 1 and 100: n and k
• n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.

The input ends with a pair of -1's.

Output Specification

For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input

3 1
1 2 5
10 11 6
12 12 7
-1 -1

Output for Sample Input

37

 dfs+记忆化搜索+回溯~~

当你非常肯定思路对，还一直wa的时候，首先看看自己定义的变量....是不是有的ambiguous。。。

~~~~~栽坑无数次了，可张点心吧~~~~~

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,k,a[110][110];
int book[110][110];
int f[4][2]= {-1,0,1,0,0,1,0,-1};
int dfs(int p,int q)        ///注意！！习惯于一直定义i，j的小可爱们，下面定义的变量要避开i，j啊~~~~坑死我了哟。。。。
{
    if(book[p][q])return book[p][q];   ///记忆化搜索
    int ans=0;
    for(int i=0; i<4; i++)    ///4个方向
    {
        for(int j=1; j<=k; j++) ///移动步数
        {
            int dp=p+f[i][0]*j;
            int dq=q+f[i][1]*j;
            if(dp<0||dq<0||dp>=n||dq>=n||a[dp][dq]<=a[p][q])continue;
                                                    ///下一个值必须大于上一个值
            ans=max(ans,dfs(dp,dq));   ///dp，dq这一步选与不选
        }
        book[p][q]=ans+a[p][q];///加上此刻位置的奶酪数
    }
    return book[p][q];
}
int main()
{
    while(~scanf("%d %d",&n,&k))
    {
        if(n==-1&&k==-1)break;
        memset(book,0,sizeof(book));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&a[i][j]);
        printf("%d\n",dfs(0,0));
    }
    return 0;
}

 

 附本篇图片：

啦啦啦~\(≧▽≦)/~啦啦啦

继续努力吖！~

再次看到这张图片，上面的字，每次读都觉得写得真好，有道理~每次读 每次都有更深的感悟！

还有啊....这上面的字体~带有小树叶....真清新可爱，可惜了  出门不带脑子得我，做滴滴下车给忘拿了.....就（*）当做给下一个人的礼物了吧~~~（黑脸....），虽然手机价值很高，而且最重要的还是穷孩子自己攒的money自己买的~~~~~~(>_<)~~~~，但是相比丢失的手机，我更心疼的是丢失的那些信息啊~~...用了半年多，都形成依赖了，做什么都是备忘录....总觉得备忘录比脑子可靠........啊啊啊啊啊，大错特错啊~~~~还是记在自己脑子里的东西不会被（偷走）~~~所以啊......血淋淋的教训，脑子时刻都要带上的！！！（破财消灾破财消灾对对对破财消灾~心情好多了~....T_T）努力学习，努力成长，！还有我人生第一次自己一个人到外省旅行的六七百张图片的记录啊~~~心疼，看过的都是风景，走过的都是路人！且行且珍惜！

还有得到的教训就是........学习的知识远远不够......尤其网络安全！！！有时候想当一个黑客！嘻嘻嘻.....算了还是学好算法，努力程序设计吧！

适当的清空一下自己，也好！！n(*≧▽≦*)n........杂乱的生活不论有没有画上完美的句点，都已经结束！over over！~

积极的人总能在每一次忧患中都看到一个机会，而消极的人则在每个机会都看到某种忧患。

————  佚名

开心点啦~\(≧▽≦)/~

好好学习，天天向上！