#P2472. [SCOI2007] 蜥蜴
[SCOI2007] 蜥蜴
题目描述
在一个 行 列的网格地图中有一些高度不同的石柱,第 行 列的石柱高度为 。
一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。
每行每列中相邻石柱的距离为 ,蜥蜴的跳跃距离是 ,即蜥蜴可以跳到平面距离不超过 的任何一个石柱上。
石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减 (如果仍然落在地图内部,则到达的石柱高度不变)。
如果该石柱原来高度为 ,则蜥蜴离开后消失,以后其他蜥蜴不能落脚。
任何时刻不能有两只蜥蜴在同一个石柱上。
输入格式
输入格式
输入第一行为三个整数 ,即地图的规模与最大跳跃距离。
接下来 行每行 个数字为石柱的初始状态, 表示没有石柱,否则表示石柱的初始高度 。
接下来 行每行 个字符为蜥蜴位置,L
表示蜥蜴,.
表示没有蜥蜴。
输出格式
输出仅一行,包含一个整数,即无法逃离的蜥蜴总数的最小值。
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
1
提示
对于 的数据满足:,,。