为了让问题更简单,小Q把道路视为
小Q现在要在道路上设置一些路灯, 对于安置在
但是有个限制,不需要照亮的格子上面不能放置路灯。
小Q希望能安置尽量少的路灯照亮所有 '.' 区域, 希望你能帮他计算一下最少需要多少盏路灯。
第一行一个正整数
第二行为一个长度为的字符串,仅由 '.' 和 'X' 这两种字符组成。
数据范围:
最少需要放置的路灯数量
5 .X.X.
3
由于不需要照亮的格子上面不能放置路灯,所以必须在1,3,5这三个位置放置路灯
5 .....
2
在2,4这两个位置放置路灯即可。
这道题你会答吗?花几分钟告诉大家答案吧!