花生(The Peanuts)
时间限制: 1 Sec 内存限制: 128 MB提交: 3 解决: 2
[提交][状态][讨论版]
题目描述
鲁宾逊先生和他的宠物猴，多多，非常喜欢花生。有一天，他们两个正沿着乡间小路散步，多多突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！”。你可以想象当时鲁宾逊先生和多多是多么的高兴！
在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图(a)所示）。在每个交叉点，有零颗或多颗花生。例如在图(b)中，只有4个交叉点上有多颗花生，分别为15，13，9和7颗，其他交叉行都只有零颗花生。多多只能从一个交叉点跳到它的四个相邻交叉点上，所花费的时间为1个单位时间。以下过程所花费的时间也是1个单位时间：从路边走到花生田，从花生田走到路边，采摘一个交叉点上的花生。
根据鲁宾逊先生的要求，多多首先走到花生数最多的植株。采摘这颗植株的花生后，然后走到下一个花生数最多的植株处，如此等等。但鲁宾逊先生并不耐烦，来等多多采摘所有的花生。而是要求多多在给定的时间内返回到路边。例如，在图9.8(b)中，多多在21个单位时间内可以采摘到37颗花生，多多走到路线如图所示。
你的任务是，给定花生分布情况，以及给定时间限制，求多多最多能摘到的花生数。你可以假定每个交叉点的花生数不一样，当然除了花生数为0外。花生数为0的交叉点数目可以有多个。
输入
输入文件的第1行为一个整数T，代表测试数据的数目，1≤T≤20。对每个测试数据，第1行包含3个整数：M、N和K，1≤M，N≤50，0≤K≤20000。接下来有M行，每行有N个整数。每个整数都不超过3000。花生田的大小为M×N，第i行的第j个整数X表示在(i，j)位置上有X颗花生。K的含义是多多必须在K个单位时间内返回到路边。
输出
对每个测试数据，输出多多在给定时间内能择到花生的最大数。
样例输入
2
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
样例输出
37
28
提示
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 struct node 8 { 9 int x,y,v;//x存行，y存列 10 }b[2505]; 11 bool cmp(node aa,node bb) 12 { 13 return aa.v>bb.v; 14 } 15 int main() 16 { 17 int t; 18 cin>>t; 19 while(t--) 20 { 21 int n,m,k; 22 cin>>n>>m>>k; 23 int l=1; 24 for(int i=1;i<=n;i++) 25 { 26 for(int j=1;j<=m;j++) 27 { 28 int aa; 29 cin>>aa; 30 b[l].x=i; 31 b[l].y=j; 32 b[l++].v=aa; 33 } 34 } 35 sort(b+1,b+1+n*m,cmp);//从小到大排序 36 int temp=0; 37 int sum=0; 38 for(int i=1;i<=n*m;i++) 39 { 40 if(b[i].v==0) 41 { 42 break;//没有可以走的了 43 } 44 if(i==1) 45 { 46 sum=1+b[i].x; 47 temp=b[i].v;//存得到的花生 48 } 49 else 50 { 51 int cz=abs(b[i].x-b[i-1].x)+abs(b[i].y-b[i-1].y)+1;//走到下一个点的时间 52 if(sum+cz>k) break; 53 if(sum+cz+b[i].x>k) break;//从这个点到那个点再到公路的时间有没有超时 54 temp+=b[i].v; 55 sum+=cz; 56 } 57 } 58 cout<<temp<<endl; 59 } 60 return 0; 61 }