G - 塔防游戏

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