Preparing NOJ

G - 塔防游戏

1000ms 65536K

Description:

   在一张N*M的地图上经行塔防游戏,地图的每个格子可能是如下三种元素之一:

    '*':代表空白

    'O':代表一个目标物

    'X':代表一个障碍物

    假设现在有一些具有相同射程R的塔。定义地图中两个之间的距离为:

            dist(G1,G2)=|R1-R2|+|C1-C2|

    其中,Ri,Ci为Gi的行号和列号(从0开始)。

    每个塔可以攻击所有与其距离小于等于R的目标物,并且对目标造成1点伤害。每一个空白格子最多放置一个塔,给定一张地图、塔的射程以及塔的个数,你能够计算出这张地图上所有目标物能够受到的最大伤害总和吗?


Input:

   第一行包含4个整数:N,M,T,R(1<=N,M,T<=1000,1<=R<=1e8)。其中,N和M分别表示地图的行数和列数;T表示塔的个数;R表示每个塔可以攻击的最大距离。

    接下来N行,每行含有一个长度为M的字符串,表示这张地图。

Output:

    一个整数,表示可以得到的最大伤害。

Sample Input:

3 3 2 1
*O*
OXO
***

Sample Output:

4

Note:

undefined

本题由旧版NOJ导入,来源:NJU 7th ACM contest

Info

NOJ

Provider NOJ

Code NOJ1179

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet