小岛的塔防游戏
描述
小岛玩的塔防游戏是一个经典的电脑游戏, 尤其受到学生的欢迎.
在游戏中有一张N*M的地图,地图的每个格子内可能是如下三种元素之一:
1) '*' : 代表空白区域
2) 'O' : 代表一个目标物
3) 'X' : 代表一个障碍物
例如, 下面就是一张塔防地图:
**O**
*OXO*
*****
**O**
假设现在有一些具有相同射程R的塔. 定义地图中两格之间的距离为:
dist(G1,G2) = |R1-R2| + |C1-C2|
其中, R1, C1 分别是G1格所在的行号和列号, R2, C2 分别是G2格所在的行号和列号(最上方的行号为0, 最左方列号为0)
每个塔可以攻击所有与其距离小于等于R的目标物, 并且对目标物造成1点的伤害.
每一个空白格子最多放置一个塔, 已经放有障碍物的格子或者放有目标物的格子里不能再放塔.
现在给定一张地图, 塔的射程以及塔的个数, 你能够计算出这张地图上所有目标物能够受到的最大伤害总和吗?
格式
输入格式
第一行包含4个整数, N, M, T, R. 其中N和M分别表示地图的行数和列数, T表示塔的个数, R代表每一个塔可以攻击目标的最大距离.
接下来N行,每行含有一个长度为M的字符串, 表示这张地图.
输出格式
一个整数, 表示可以得到的最大伤害
样例1
样例输入1
3 3 2 1
*O*
OXO
***
样例输出1
4
限制
对于40%的数据: 1<=N,M,R<=100.
对于100%的数据: 1<=N,M<=1000, 1<=T<=1000, 1<=R<=10^8, 所有答案均保证在64位带符号长整型范围内.
每一个测试点的时间限制为1秒.
信息
- ID
- 1877
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 280
- 已通过
- 32
- 通过率
- 11%
- 被复制
- 3
- 上传者