本文共 1728 字，大约阅读时间需要 5 分钟。

题目描述

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。

我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

1. 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2. 从一棵植株跳到前后左右与之相邻的另一棵植株；
3. 采摘一棵植株下的花生；
4. 从最靠近路边（即第一行）的某棵花生植株跳回路边。
   现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
   

例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。

输入

第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N <= 20），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。

输出

输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数

思路

1. 用一个结构体数组将花生田里的有花生的植株的位置和花生数存起来
2. 然后按花生数从大到小排序。
3. 初始化：将多多的坐标先定为0行 花生数第一大的植株的列。
4. 循环判断可不可以摘剩下的最大的那个花生：
   当前点到目标点的时间（3.中提前定义过）+1（采摘时间）+回程时间（其实就是目标点的行）<=剩余时间
   然后剩余时间减去（到达目标时间+1）
   答案+目标点的花生数。
   位置调整。

代码

将就着看吧。。。重点看思路 （啊我太懒了）

#include
   
    #include
    
     #include
     
      using namespace std;struct kk{                       //x行y列的植株有z个花生   int z,x,y;} k[1001];bool cc(kk a,kk b){             //定义，按花生数从大到小排序   return a.z>b.z;}int a,n,m,t,tt=0,ans=0;int main(){      scanf("%d%d%d",&n,&m,&t);   for(int i=1;i<=n;++i)     for(int j=1;j<=m;++j){     //单纯一个读入     	scanf("%d",&a);     	if(a!=0){                //如果当前植株有可采摘的花生。     		tt++;     		k[tt].z=a;     		k[tt].x=i;     		k[tt].y=j;     	}     }   sort(k+1,k+1+t,cc);            int i=1,wi=0,wj=k[1].y;   while(i<=tt&&abs(k[i].x-wi)+abs(k[i].y-wj)+k[i].x+1<=t){       	t=t-abs(k[i].x-wi)-abs(k[i].y-wj)-1;   	wi=k[i].x;   	wj=k[i].y;   	ans+=k[i].z;   	i++;   }   printf("%d",ans);   return 0;}