#4901. 周记祷蛋

周记祷蛋

题目描述:

在一个N*M的矩形区域中,分布着敌人和友军,由于敌人太多,我方准备使用【周记祷蛋】攻击敌人,【周记祷蛋】的伤害半径为K,若在矩阵的(x,y)处释放【周记祷蛋】,所有距离(x,y)曼哈顿距离小于K的位置都将被毁灭。

【周记祷蛋】威力巨大容易误伤友军,指挥官要求释放时不可以波及友军,同时为了不浪费输出,指挥官希望【周记祷蛋】攻击范围内任意位置都存在敌军。

问矩阵中有多少个满足指挥官要求的位置。

任意两点(x,y),(a,b)曼哈顿距离为|x-a|+|y-b|

输入格式:

第一行输入三个数N M KN\ M\ K

接下来n行每行一个字符串表示地图,敌军用o表示,友军用x表示

输出格式:

一个整数表示答案

样例:

4 5 2
xoooo
oooox
ooooo
oxxoo
3

可行方案及位置如下,用*表示攻击范围

x	*	o	o	o
*	*	*	o	x
o	*	o	o	o
o	x	x	o	o

x	o	*	o	o
o	*	*	*	x
o	o	*	o	o
o	x	x	o	o

x	o	o	o	o
o	o	o	*	x
o	o	*	*	*
o	x	x	*	o
8 6 3
oooooo
oooooo
oooooo
oooooo
oxoooo
oooooo
oooooo
oooooo
4

提示

对于10%的数据,图中无友军

对于100%的数据,3<=N,M,K<=500NMK<=1e83<=N,M,K<=500,N*M*K<=1e8