题目描述
给定一个数组，从第一个开始，正好走到数组最后，所使用的最少步骤数。
要求：
第一步从第一元素开始，第一步小于<len/2（len为数组的长度）。从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少, 如果目标不可达返回-1，输出最少的步骤数，不能往回走。
输入
7 5 9 4 2 6 8 3 5 4 3 9
输出
2
输入
1 2 3 7 1 5 9 3 2 1
输出
-1
输入
7, 1, 1, 1, 1, 2, 1, 2, 3, 2, 1, 9
输出
4
思路
思路一：从前往后，因为第一步小于<len/2，所以先把从第0到len/2-1步放入路径，然后从这些路径往后走，第一个达到终点的则为最短。
思路二：从后往前，找到所有前面能走到终点的点，放入可到达位置，然后又从以刚刚找到的可达路径为终点，找到前面能走到当前终点的所有可达位置，直到走到小于len/2的位置，当前走的步数就是最短步数。
方案一二对比：方案一在每一步走的时候，在未达终点前，都不会移除无效数据，方案二在每一次走的时候其实都会筛选掉一些到不了当前位置的点，越算越快。但是具体没有细研究。
我采用的是方案二思路
void ReachDest(std::vector<int>& way)
{
int step = 0;
std::vector<int> allend(1, way.size() - 1);
int len = way.size();
while (true)
{
std::vector<int> newend;
++step;
for (auto oneend : allend)
{
for (int i = oneend - 1; i >= 0; --i)
{
if (oneend - i == way[i])
{
if (i < len/2)
{
std::cout << ++step << std::endl;
return;
}
newend.push_back(i);
}
}
}
if (newend.empty())
break;
allend = newend;
}
std::cout << -1 << std::endl;
}