[FZYZOJ 1273]坦克游戏

Grade 0 Open Time Wednesday, 16 January 2013, 11:35 am
Discount 0.8 Time Discount Wednesday, 16 January 2013, 11:35 am
Allow late Yes Close Time Wednesday, 16 January 2013, 11:35 am
Input file gametk.in Output file gametk.out

【问题描述 】

NOI2008公司最近推出了一款新的坦克游戏。在游戏中,你将操纵一辆坦克,在一个 N × M 的区域中完成一项任务。在此的区域中,将会有许多可攻击的目标,而你每摧毁这样的一个目标,就将获得与目标价值相等的分数。只有获得了最高的分数,任务才算完成。同时,为了增加游戏的真实性和难度,该游戏还做了以下的限制:

• 坦克有射程 r 的限制。为方便计算,射程 r 规定为:若坦克位于 (x,y) 格,则它可攻击的目标 (x1,y1) 必须满足 |x-x1|,|y-y1| ∈ [0,r] 。

• 对坦克完成任务的时间有严格限制,规定为 t 秒。其中,坦克每进行一次移动都需 1 秒的时间,每攻击一个目标也需 1 秒的时间。时间一到 t 秒,便对此次任务进行记分。

• 坦克最初位于左上角,且移动方向只准是向右或向下,每次只允许移动一格。

在以上的限制条件下,要完成该任务便成为了一件很难事情。因此,你必须为此编写一个程序,让它助你完成这个艰巨的任务。

【输入格式】

输入文件: gametk.in

第一行右四格整数 N 、 M 、 r 、 t ,分别表示区域的长、宽,以及射程和完成任务时间。

接下来 N 行是一格 N×M 的矩阵,对应每个位置上目标的价值。 1 ≤ N 、 M ≤ 500 , 1 ≤ r ≤ 100 , 1 ≤ t ≤ 2500 。

【输出格式】

输出文件: gametk.out

输出文件仅一个数 max ,即该任务中可得到的最高分数。

【输入样例】

5 5 2 7
0 5 0 0 4
0 0 0 0 2
0 0 0 0 0
0 0 0 0 0
5 0 3 0 11

【输出样例】

21