poj 1928

题意：题意：dodo要在规定时间内拿peanut，每次拿peanut都是从最多的那堆拿起，因此需要将peanut的数量从大到小排序，
走路的规则：
1.从road走到field需要一个单位时间
2.在方格内走每一个格的时间是一个单位时间
3.每捡起一堆peanut要用一个单位时间
4.从field走到road需要一个单位时间

思路：题目中提到"根据鲁兵逊先生的要求,多多首先走到花生最多的植株,采摘这颗植株的花生后,走到下一个花生数最多的植株处,如此等等",所以,只需把花生数按从大到小的顺序进行排序,在满足时间限制的前提下依次采摘花生即可,因此可以定义一个结构体,表示网格中的节点,它包含3个成员,节点的x,y坐标,及花生数.在排序时,对节点数组按花生数进行一级排序,即按花生数从大到小排序.

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

struct  point 
{
	int x1,y1;
	int value;
}p[2510];
int cmp(const void *a,const void *b)
{
	struct point *e1=(point *)a;
	struct point *e2=(point *)b;
	return (e2->value)-(e1->value);
}

int main()
{
	int cases;
	int i,j,m,n,k,t,total,x,y,c;
	cin>>cases;
	while (cases--)
	{
		cin>>m>>n>>k;
		c=1;
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
			{
				cin>>p[c].value;
				p[c].x1=i;
				p[c].y1=j;
				c++;
			}
			qsort(&p[1],m*n,sizeof(p[1]),cmp);
			t=0;
			x=0;
			i=1;
			total=0;
			while (t<k)
			{
				if(p[i].value==0)
					break;
				if(x==0)
					y=p[i].y1;
				if(t+p[i].x1+1+abs(p[i].x1-x)+abs(p[i].y1-y)<=k)
				{
					t+=1+abs(p[i].x1-x)+abs(p[i].y1-y);
					x=p[i].x1;
					y=p[i].y1;
					total+=p[i].value;
				}
				else
					break;
				i++;

			}
			cout<<total<<endl;
	}
	return 0;

}