鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生(
也就是说，即便20不能被采摘，也不能采摘小于20的花生，最后的时间可能会剩余，这是不同于NYOJ 106贪心背包问题的)；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1.从路边跳到最靠近路边（即第一行）的某棵花生植株；
2.从一棵植株跳到前后左右与之相邻的另一棵植株；
3.采摘一棵植株下的花生；
4.从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
【输入】
n 输入第一行包括三个整数，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表示该植株下没有花生。
【输出】
n 输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。
//类似背包问题的解决办法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct DATA
{
int num;
int x,y;//花生位置
}DATA;
/*
结构体的话，用一维数组
否则二维数组，这道题来说，因为要排序 且
涉及到位置的转换，结构体更方便
*/
DATA ch[3000];
int cmp(const void *a,const void *b)
{
//((DATA *)b),外层的括号是必须的
return ((DATA *)b)->num-((DATA *)a)->num;
}
int main()
{
int i,j,k,T;
int m,n,k0,cnt,total,temp;
scanf("%d",&T);
while(T--)
{
cnt=0;//耗费时间
total=0;//花生数目
temp=0;//路到节点移动时间
memset(ch,0,sizeof(ch));
scanf("%d%d%d",&m,&n,&k0);
/*
for(i=0;i<m*n;i++)
{
scanf("%d",&ch[i].num);
下面的两行大错特错，横坐标会0,1,2……m-1循环变化，实际应是000000,11111……
ch[i].x=i%m;
ch[i].y=i%n;
}
*/
k=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
ch[k].x=i;
ch[k].y=j;
scanf("%d",&ch[k++].num);
}
qsort(ch,m*n,sizeof(DATA),cmp);//sizeof(DATA),不是int
/*
printf("\n\n\n");
k=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%d %d %d ",ch[k++].num,ch[k].x,ch[k].y);
printf("\n");
}
*/
//类似背包问题的解决办法
for(i=0;ch[i].num!=0&&cnt<k0;i++)//第一个条件防止死循环（如果采摘完了，仍有时间）
{
//printf("total=%d cnt=%d\n",total,cnt);
if(i!=0)
temp=abs(ch[i+1].x-ch[i].x)+abs(ch[i+1].y-ch[i].y);
if(0==i)
{
if(2*(ch[i].x+1)+1>k0)
break;
else if(2*(ch[i].x+1)+1==k0)
{
total+=ch[i].num;
break;
}
else
{
cnt+=ch[i].x+1+1;//1为本次采摘时间
total+=ch[i].num;
temp=abs(ch[1].x-ch[0].x)+abs(ch[1].y-ch[0].y);
if(cnt+temp+1+ch[i+1].x+1<=k0)//是否采摘下个节点 ，第一个1为下次采摘时间
{
total+=ch[i+1].num;
cnt+=temp+1;
}
else
break;
}
}
else if(cnt+temp+1+ch[i+1].x+1<=k0)//是否采摘下个节点
{
total+=ch[i+1].num;
cnt+=temp+1;
}
else
break;
}
printf("%d\n",total);
}
system("pause");
return 0;
}
