有一个青蛙生活在一条横轴上,它需要到达位于点 n 的家。它从点 1 开始。青蛙可以向右跳跃,跳跃的最大距离为 d。因此,从点 x 跳跃后,它可以到达点 x + a,其中 a 是从 1 到 d 的任意整数。
对于从 1 到 n 的每个点,已知该点是否有睡莲。青蛙只能跳到有睡莲的点。保证在点 1 和点 n 处都有睡莲。
确定青蛙从点 1 到达家(即点 n)所需的最小跳跃次数。如果青蛙无法到达家,则输出 -1。
有一个青蛙生活在一条横轴上,它需要到达位于点 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 所需的最小跳跃次数。
8 4 10010101
2
4 2 1001
-1
8 4 11100101
3
12 3 101111100101
4