1116. 扔手雷

小明很喜欢吃鸡,他特别喜欢扔手雷攻房。现在他想知道在 N \times M 大小的房间范围内,扔一枚爆炸范围为 R 的手雷,能杀死多少敌人。

假设在手雷爆炸范围内的人都会被炸死。

输入

第一行:三个整数 N,M,R \ ( 1 \leq N,M,R \leq 1000 )。表示房间范围 N \times M,手雷半径是 R

接下来 N 行每行 M 个字符。# 代表空地,X 表示敌人,O 表示手雷位置。

输出

输出一个整数,能杀死的敌人数量。

样例

标准输入 复制文本
4 5 1
XX##X
XO##X
##X##
#####
标准输出 复制文本
2

提示

第一行第一列的敌人和手雷的距离为 \sqrt{2}

来源

2018 软件学院蓝桥杯热身赛 (For 18SEer only)

单点时限 1 秒
内存限制 128 MB
提交 358
通过 139