pku1928.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int n_nuts;
	int x, y;	
} Point;

int nuts[50][50];
Point p[2500];
int time, allX, allY;

int cmp(const void *a, const void *b)
{
	Point *c = (Point *)a;
	Point *d = (Point *)b;
	return d->n_nuts - c->n_nuts;	
}

int calc(int k)
{
	int i, num, t, tmp_t;
	t = 0;
	tmp_t = (p[0].y + 1) * 2 + 1;
	if (tmp_t <= time - t)
	{
		t += p[0].y + 2;
		num = p[0].n_nuts;	
	}
	else
	{
		printf("0\n");
		return 0;	
	}
	for (i = 1; i < k; i++)
	{
		tmp_t = abs(p[i-1].x - p[i].x) + abs(p[i-1].y - p[i].y) + 1;
		if (tmp_t + p[i].y + 1 <= time - t)
		{
			t += tmp_t;
			num += p[i].n_nuts;
		}
		else
		{
			break;	
		}	
	}
	printf("%d\n", num);
	return 0;		
}

int main()
{
	int i, j, k, t, tmp;
	
	scanf("%d", &t);
	
	while (t--)
	{
		scanf("%d%d%d", &allY, &allX, &time);
		for (i = 0, k = 0; i < allY; i++)
		{
			for (j = 0; j < allX; j++)
			{
				scanf("%d", &tmp);
				if (tmp == 0) continue;
				p[k].n_nuts = tmp;
				p[k].x = j;
				p[k].y = i;
				k++;	
			}	
		}
		qsort(p, k, sizeof(p[0]), cmp);
		calc(k);	
	}
	return 0;
}