#P2081. 青蛙回家
青蛙回家
题目描述
一只青蛙现在在一个数轴上,它现在要从点 跳到点 ,它每次可以向右跳不超过 个单位。比如,它可以从点 跳到点 。特别的,青蛙只能在有百合花的点上停留。保证点 和点 之间有一些点有百合花。请输出青蛙到达点 的最小跳跃次数。
输入输出格式
输入格式
输入的第一行包括两个正整数 和 。
输入的第二行是一个长度为 的无空格字符串,由0
和1
组成,表示哪些点上有百合花(1
表示有)。保证点 和点 有百合花。
输出格式
输出青蛙的最小跳跃次数。如果它不可能到达,输出-1。
输入输出样例
样例 #1
样例输入 #1
8 4
10010101
样例输出 #1
2
样例 #2
样例输入 #2
4 2
1001
样例输出 #2
-1
样例 #3
样例输入 #3
8 4
11100101
样例输出 #3
3
样例 #4
样例输入 #4
12 3
101111100101
样例输出 #4
4
说明
在样例1中,青蛙可以从点 跳3个单位到点 ,再从点 跳4个单位到点 . 在样例2中,青蛙不能到达点 ,因为它至少需要跳3个单位,但它最多只能跳2个单位。