【背景】
2008.11.16
3721大班在Mr Lv 的组织下，到六食堂举办了一次集体包饺子活动：）
这次活动很成功，大家都很高兴，所谓“有缘千里，相聚北航”。
下来后，某人根据这次活动出了一套练习题……
------------------------------------------------
o(∩_∩)o…哈哈，这个活动好玩，每个小班派个代表，比赛谁在30秒（还是1分钟？）内吃的饺子数目最多，可以喝水！
最后的胜利者是Mr Wang吧，当“采访”的时候他一语道破了成功秘诀：
“其实当比赛开始前我做了一些工作；
有很多盘饺子放在我面前吧，我会先选择一些盘吃，毕竟时间不多，换盘子要时间；
我选择的规则是：
首先先把我面前的平面划分成N*M个方格，某些方格中有盘子，并且知道盘子中饺子的数量；对于没有盘子的位置，记为0；
然后从最多到最少饺子数量来选择好盘数，我估计我可以干掉R盘，所以只选择R盘；
但是有一点，两盘之间的距离如果大于了P，我就不会选择下一盘，跳过去，直到按照排序下来某个盘的距离小于等于P；
详细解释下：比如我吃第i盘的时候位置是（3，3），按照排序下一盘位置是（1，1），但是P是2，我就不会选择了，这里P定义为|x1-x2|+|y1-y2|，直接跳到下面一盘，就是按照饺子个数从大到小排序好的序列，假设这个盘子位置是（3，2）那么就可以选择作为第I+1盘饺子了；
当然如果按照这个规矩选择下来不足R盘也算了……
恩~谢谢党和人民，谢谢Mr. Lv 给我这个证明自己算法正确的机会……
”
头晕了吧……现在作为评委，请你按照这个规矩计算出他吃的饺子数目；
- 输入
-
输入数据第一行包含一个整数T，表示有T组测试数据；
对于每组测试数据：
第一行包含4个整数N,M,R,P。各个数据含义如题；
接下来是个N*M的矩阵，各个元素是一个非负整数；
保证N和M均小于等于100，R小于N*M，P大于0；
这里为了没有歧义，保证每个盘子中饺子数目都不相等；
- 输出
-
请按照题目描述规则输出大胃王吃掉的饺子个数；
- 样例输入
-
1
-
5 5 3 3
-
0 0 0 0 2
-
0 5 0 0 0
-
0 0 1 0 0
-
3 0 0 4 0
-
0 0 0 0 0
- 样例输出
-
9
-
（解释：5+3+1）
模拟题
#include <iostream>
#include <cstdio>
#include<algorithm>
using namespace std;
struct node{
int x;
int y;
int data;
};
node a[10001];
bool cmp(node a, node b)
{
return (a.data > b.data);
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n, m, r, p;
scanf("%d%d%d%d", &n, &m, &p, &r);
int i, j, k;
k = 0;
for(i = 0; i != n; i ++)
for(j = 0; j != m; j ++)
{
scanf("%d", &a[k].data);
if(a[k].data != 0)
{
a[k].x = i;
a[k].y = j;
++ k;
}
}
sort(a, a + k, cmp);
j = 0;
int sum = 0;
sum += a[j].data;
node temp;
temp = a[j];
++ j;
int amount = 1;
while(amount < p)
{
if(abs(a[j].x - temp.x)+ abs(a[j].y - temp.y) <= r)
{
sum += a[j].data;
temp = a[j];
amount ++;
}
j ++;
if(j > k)
break;
}
printf("%d\n", sum);
}
return 0;
}