问题 6797 --回家的路

6797: 回家的路

时间限制: 1 Sec  内存限制: 256 MB
提交: 49  解决: 23
[提交][状态][命题人:]

题目描述

有一个青蛙生活在一条横轴上,它需要到达位于点 n 的家。它从点 1 开始。青蛙可以向右跳跃,跳跃的最大距离为 d。因此,从点 x 跳跃后,它可以到达点 x + a,其中 a 是从 1 到 d 的任意整数。

对于从 1 到 n 的每个点,已知该点是否有睡莲。青蛙只能跳到有睡莲的点。保证在点 1 和点 n 处都有睡莲。

确定青蛙从点 1 到达家(即点 n)所需的最小跳跃次数。如果青蛙无法到达家,则输出 -1。

输入

输入的第一行包含两个整数 n 和 d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) —— 青蛙想要到达的点,以及青蛙最大跳跃的长度。

第二行是一个长度为 n 的字符串 s,由 0 和 1 组成。如果字符串中的某个字符为 0,则对应的点没有睡莲;如果为 1,则表示该点有睡莲。保证字符串的第一个和最后一个字符均为 1。

输出

如果青蛙无法到达家,则输出 -1。

否则,输出青蛙从点 1 到达点 n 所需的最小跳跃次数。

样例输入
Copy
8 4
10010101
样例输出
Copy
2

提示

Input
4 2
1001
Output
-1
Input
8 4
11100101
Output
3
Input
12 3
101111100101
Output
4

来源

 

[提交][状态]