首页 > 代码库 > 花生采摘

花生采摘

2024-07-31 11:21:22   219人阅读

 

 

 

Mr. Robinson and his pet monkey Dodo love peanuts very much. One day while they were having a walk on a country road, Dodo found a sign by the road, pasted with a small piece of paper, saying "Free Peanuts Here! " You can imagine how happy Mr. Robinson and Dodo were.        
There was a peanut field on one side of the road. The peanuts were planted on the intersecting points of a grid as shown in Figure-1. At each point, there are either zero or more peanuts. For example, in Figure-2, only four points have more than zero peanuts, and the numbers are 15, 13, 9 and 7 respectively. One could only walk from an intersection point to one of the four adjacent points, taking one unit of time. It also takes one unit of time to do one of the following: to walk from the road to the field, to walk from the field to the road, or pick peanuts on a point.        
According to Mr. Robinson‘s requirement, Dodo should go to the plant with the most peanuts first. After picking them, he should then go to the next plant with the most peanuts, and so on. Mr. Robinson was not so patient as to wait for Dodo to pick all the peanuts and he asked Dodo to return to the road in a certain period of time. For example, Dodo could pick 37 peanuts within 21 units of time in the situation given in Figure-2.        
Your task is, given the distribution of the peanuts and a certain period of time, tell how many peanuts Dodo could pick. You can assume that each point contains a different amount of peanuts, except 0, which may appear more than once.        

Input

The first line of input contains the test case number T (1 <= T <= 20). For each test case, the first line contains three integers, M, N and K (1 <= M, N <= 50, 0 <= K <= 20000). Each of the following M lines contain N integers. None of the integers will exceed 3000. (M * N) describes the peanut field. The j-th integer X in the i-th line means there are X peanuts on the point (i, j). K means Dodo must return to the road in K units of time.      

Output

For each test case, print one line containing the amount of peanuts Dodo can pick.      

Sample Input

26 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 06 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0

Sample Output

3728


题目大意：尽可能多的摘花生；但是保证以下两点：
          1、不要超时间（时间计算：每移动一下或者摘一次花生为一个单位时间）
          2、要按照从多到少的顺序摘花生。

代码及分析（Runtime Error）：
 1 #include<stdio.h> 2 #include<algorithm> 3 #include<math.h> 4 using namespace std; 5 struct pea{ 6     int gains; 7     int x; 8     int y; 9 }peanut[21*21];  10  //（x,y)记录花生的位置，y平行于大路；gains记录花生结的果实11 bool cmp(pea a,pea b){12     return a.gains>b.gains;13 }14 int main()15 {16     int M,N,K,T;17     //M,N表示花生地的长（平行于x）和宽（平行于y）；18     //K表示时间限制；T表示测试组数；19     scanf("%d",&T);20     while(T--){21         scanf("%d%d%d",&M,&N,&K);22         int i,j,k,gains=0;//gains表示收获的花生；23         for(i=0,k=0;i<M;i++)24             for(j=0;j<N;j++,k++){//输入花生地的信息25                 scanf("%d",&peanut[k].gains);26                 peanut[k].x=i,peanut[k].y=j;27             }28         sort(peanut,peanut+k,cmp);//将花生按照果实多少排序29         int timeused=peanut[0].x+1+1;    //第一次用时；30         if(timeused+timeused+peanut[i].x+1<=K){31             //判断第一次会不会超时，32             for(i=0;timeused+peanut[i].x+1<=K;i++){//如果不超时，则自动搜寻下一个目标。。。33                 gains=gains+peanut[i].gains;34                 timeused=timeused+(abs(peanut[i+1].y-peanut[i].y)+1+abs(peanut[i+1].x-peanut[i].x+1));35             }36             printf("%d\n",gains);37         }38     }39     return 0;40 }


解题心得：这还是体力活，虽然题没有AC，但是的确学到了很多东西。


花生采摘


联系
我们