The Way to Home

The Way to Home A - The Way to Home

题目翻译
一只青蛙生活在 Ox 轴上，需要到达位于 n 点的家。 她从点 1 开始。青蛙可以在不超过 d 的距离处向右跳。 所以，她从点 x 跳跃后，可以到达点 x + a，其中 a 是从 1 到 d 的整数。

对于从 1 到 n 的每个点，都知道其中是否有一朵百合花。 青蛙只能用百合花点跳。 保证1点和n点都有百合花。

确定青蛙需要到达家的最小跳跃次数，即从点 1 到点 n 处。考虑最初青蛙在点 1。如果青蛙无法到达家，则打印 -1。

题目分析
搜索每种情况+贪心

代码

#include
using namespace std;
char a[10001];
int res = 0,flag=1;
int main()
{
	int n, m, k;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	if (a[0] == '0' || a[n-1] == '0')
	{
		cout << -1;
		return 0;
	}
	for (int i = 0; i < n-1;)
	{
		k = i;
		for (int j = m; j > 0; j--)//每一步都先往最远的地方
		{
			if (a[i + j] == '1')
			{
				k = i + j;
				res++;
				break;
			}
		}
		if (k == i)
		{
			cout << -1;
			return 0;
		}
		i = k;
	}
	cout << res;
	return 0;
}