3244: 05-27-D04-花生(L4)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
在一块花生田里，花生植株整齐地排列成矩形网格，如图(a)所示。在每个交叉点，有零颗或多颗花生。例如在图(b)中，只有4个交叉点上有多颗花生，分别为15，13，9和7颗，其他交叉行都只有零颗花生。只能从一个交叉点跳到它的四个相邻交叉点上，所花费的时间为1个单位时间。以下过程所花费的时间也是1个单位时间：从路边走到花生田，从花生田走到路边，采摘一个交叉点上的花生。
采摘方法：首先走到花生数最多的植株；采摘这颗植株的花生后，然后走到下一个花生数最多的植株处，以此类推。要求在给定的时间内返回到路边。例如，在图(b)中，在21个单位时间内可以采摘到37颗花生，行走路线如图(b)所示。
你的任务是，给定花生分布情况，以及给定时间限制，求最多能摘到的花生数。假定每个交叉点的花生数不一样，当然花生数为0除外。花生数为0的交叉点数目可以有多个。
输入
输入数据的第1行包含3个整数：m、n和k，1≤m，n≤50，0≤k≤20000。接下来有m行，每行有n个整数。每个整数都不超过3000。花生田的大小为m×n，第i行的第j个整数X表示在(i，j)位置上有X颗花生。k的含义是必须在k个单位时间内返回到路边。
输出
输出在给定时间内能择到花生的最大数。
样例输入 复制
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0样例输出 复制
37提示
m、n和k，1≤m，n≤50，0≤k≤20000。