#4901. 周记祷蛋
周记祷蛋
题目描述:
在一个N*M的矩形区域中,分布着敌人和友军,由于敌人太多,我方准备使用【周记祷蛋】攻击敌人,【周记祷蛋】的伤害半径为K,若在矩阵的(x,y)处释放【周记祷蛋】,所有距离(x,y)曼哈顿距离小于K的位置都将被毁灭。
【周记祷蛋】威力巨大容易误伤友军,指挥官要求释放时不可以波及友军,同时为了不浪费输出,指挥官希望【周记祷蛋】攻击范围内任意位置都存在敌军。
问矩阵中有多少个满足指挥官要求的位置。
任意两点(x,y),(a,b)曼哈顿距离为|x-a|+|y-b|
输入格式:
第一行输入三个数
接下来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%的数据,
Related
In following contests: