Blog·Tanky WooABOUTRSS

百练oj 2950 摘花生

13 May 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

注意题目有一个很重要的信息:依次找到剩下植株里花生最多的。题目测试数据有点问题,没有输入T。

是一道模拟题把。

题目地址:http://poj.pku.edu.cn/problem/2950/

#include 
#include

#include 
#include 
#include 
#include 
using namespace std;

int T, M, N, K;
#define MAX_NUM 60
int aField[MAX_NUM][MAX_NUM];
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &M, &N, &K);
        for(int i = 1; i <= M; i++)
            for(int j = 1; j <= N; j++)
                scanf("%d", &aField[i][j]);
        int nCuri = 0, nCurj;
        int nTotalTime = 0;
        int nTotalPeanuts = 0;
        while(nTotalTime < K)
        {
            int maxi, maxj, max = 0;
            for(int i = 1; i <= M; i++)
                for(int j = 1; j <= N; j++)
                    if(max < aField[i][j])
                    {
                        max = aField[i][j];
                        maxi = i;
                        maxj = j;
                    }
            if(max == 0)
                break;
            //如果当前位置是在路上,
            //那么应该走到横坐标nCurj处,再进入花生地
            if(nCuri == 0)
                nCurj = maxj;
            if(nTotalTime + maxi + 1 + abs(maxi - nCuri) + abs(maxj - nCurj) <= K)
                //下一行加上走到新位置,以及摘花生的时间
            {
                nTotalTime += 1 + abs(maxi - nCuri) + abs(maxj - nCurj);
                nCuri = maxi;
                nCurj = maxj;
                nTotalPeanuts += aField[maxi][maxj];
                aField[maxi][maxj] = 0;
            }
            else
                break;
        }
        printf("%d\n", nTotalPeanuts);
    }
    return 0;
}