当前编程题：实验二 进制转换问题(16级) ---摘花生 |
| 10. | 问题描述鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”  我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；2) 从一棵植株跳到前后左右与之相邻的另一棵植株；3) 采摘一棵植株下的花生；4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图2所示的花生田里，只有位于(2， 5)， (3， 7)， (4， 2)， (5， 4)的植株下长有花生，个数分别为13， 7， 15， 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。输入形式输入的第一行包括一个整数T，表示数据组数每组输入的第一行包括三个整数，M， N和K，用空格隔开；表示花生田的大小为M * N（1 <= M， N <= 50），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i， j)下花生的数目，0表示该植株下没有花生。输出形式输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入16 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 0样例输出37两天没写代码了 心里很慌  #include<stdio.h>void seek(int aa[][50],int max,int *p,int *q,int m,int n){int i,j;for(i=0;i<m;i++){for(j=0;j<n;j++){if(aa[i][j]==max){*p=i;*q=j;break;}}}}void handle(int aa[][50],int m,int n,int time){// PRintf("%d",time); int k=0,t,pretime=0,flag=0,s=0,i,j,p,q,p0=1,q0=1,bb[50]; /* for(i=0;i<m;i++) { for(j=0;j<n;j++) { printf("%d ",aa[i][j]); } printf("/n"); } */for(i=0;i<m;i++){for(j=0;j<n;j++){if(aa[i][j]>0){bb[k]=aa[i][j];k++;}}}for(i=0;i<k-1;i++){for(j=0;j<k-1-i;j++){if(bb[j]<bb[j+1]){t=bb[j];bb[j]=bb[j+1]; bb[j+1]=t; }}}/* for(i=0;i<k;i++){printf("%d ",bb[i]);}printf("/n");*/for(i=0;i<k;i++){p=0;q=0;seek(aa,bb[i],&p,&q,m,n);p++;q++;// printf("%d %d %d %d/n",q0,time,pretime,s); if(p-p0<0) { pretime+=p0-p; } else { pretime+=p-p0; } if(q-q0<0) { pretime+=q0-q; } else { pretime+=q-q0; } p0=p;q0=q; s+=bb[i]; pretime++; if(pretime+p0>time) { printf("%d/n",s-bb[i]); flag=1; break; }}if(flag==0){printf("%d/n",s);}} /*1 20 0 02 20 4 155 20 9 284 20 13 3737*/int main(){int N,n,m,k,i,j,aa[100][50];scanf("%d",&N);while(1){if(N==0){break;}scanf("%d%d%d",&m,&n,&k);for(i=0;i<m;i++){for(j=0;j<n;j++){scanf("%d",&aa[i][j]);}}handle(aa,m,n,k);N--;}return 0;} |
新闻热点
疑难解答
