grids 2950 摘花生

题意

中文的不解释

思路

这是一道模拟题，根据查找的步骤，一次次判断能否走到，能则走，不能则结束
查找的方法为：查出为采摘的花生数量最多的，判断能否走到，并采摘，并回到路。能则进行走到那里，并采摘，不能则结束。

总结

要细心，包括以下注意的：
（1）第一次采摘能不能成功的
（2）判断能否成功还需要将返回路的计算进去
（3）采摘需要消耗一个时间

代码

I.方法一
  直接每次都求出最大值，这种方法的时间复杂度为O(N^2)

(1)C

#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define MAX 50
int p[MAX+2][MAX+2];
int main()
{
    int t;//case times 
    int m,n,k;//m*n field,k times
    int i,j;//loop tmp
    int sum;
    int max,tmpi,tmpj,tmpii,tmpjj;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        scanf("%d%d%d",&m,&n,&k);
        for(i=0;i<m;i++){ for(j=0;j<n;j++){ scanf("%d",&p[i][j]); }}
        max = -1;
        for(i=0;i<m;i++){for(j=0;j<n;j++){if(max<p[i][j]){max=p[i][j];tmpi=i;tmpj=j;}}}
        if(max==0 || k<(tmpi+1)*2 + 1){printf("0\n");}
        else
        {
            k -= (tmpi+1)+1;
            sum += max;
            p[tmpi][tmpj] = 0;
            tmpii = tmpi;tmpjj = tmpj;
            max = -1;
            for(i=0;i<m;i++){for(j=0;j<n;j++){if(max<p[i][j]){max=p[i][j];tmpi=i;tmpj=j;}}}
            while((k >= abs(tmpii-tmpi) + abs(tmpjj-tmpj) + tmpi + 1 + 1) && (max != 0))
            {
                k -= (abs(tmpii-tmpi) + abs(tmpjj-tmpj) + 1);
                sum += max;
                p[tmpi][tmpj] = 0;
                tmpii = tmpi;tmpjj = tmpj;
                max = -1;
                for(i=0;i<m;i++){for(j=0;j<n;j++){if(max<p[i][j]){max=p[i][j];tmpi=i;tmpj=j;}}}
                //printf("max=%d,sum=%d,k=%d,kk=%d\n",max,sum,    k,abs(tmpii-tmpi) + abs(tmpjj-tmpj) + tmpi + 1);
            }
            printf("%d\n",sum);
        }
    }
    //system("pause");
    return 0;
}