回家的路 - 代码源竞赛平台

题目描述

蜗蜗要沿着一条长度为 $n$ 的道路回家。道路上的位置从 1 到 $n$ 编号，字符串 s 的第 $i$ 个字符表示该位置是否可以落脚：

• 1 表示可以落脚；
• 0 表示不能落脚。

蜗蜗从位置 1 出发，每次最多向前跳 $d$ 个位置，并且只能落在字符为 1 的位置。请你求出到达位置 $n$ 所需的最少跳跃次数；如果无法到达，输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $d$。

第二行包含一个长度为 $n$ 的二进制字符串 s，保证第一个和最后一个字符均为 1。

输出格式

输出最少跳跃次数；如果无法到达位置 $n$，输出 $-1$。

样例

8 3
10010101

3

样例解释

可以依次从位置 1 跳到位置 4，再跳到位置 6，最后跳到位置 8，共需要 3 次跳跃。

数据范围

对于 100% 的数据，保证 $2\le n\le100$，$1\le d\le n$，字符串 s 的长度为 $n$，且只包含 0 和 1，首尾字符均为 1。