典型的BFS题
大体思路
把楼层抽象为一个一维数组,对应K值为行走步数,进行搜索
注:蒟蒻使用数组模拟队列
上代码: (有注释 )
#include<cstdio>
#include<cstring>
using namespace std;
int head, tail; //头尾指针
struct lift{ //存储电梯楼层
int book; //标记
int cnt; //步数
int k; //K值
}l[201];
int a, b, n; //如题
int x; //临时数据存储
int map[1002]; //队列
int main()
{
//freopen("data.in", "r", stdin);
scanf("%d%d%d", &n, &a, &b);//不多说
for(int i=1; i<=n; ++i)
{
scanf("%d", &l[i].k);
l[i].cnt = 0, l[i].book = 0;//初始化
}
head = 0, tail = 0;
l[a].book = 1, l[a].cnt = 0;
map[head] = a, ++tail; //初始点特殊处理
while(head < tail) //若还能扩展
{
x = map[head] + l[map[head]].k; //扩展方式1
if(x>=1 && x<=n && l[x].book == 0) //在范围以内且未到过
{
map[tail++] = x; //入队
l[x].book = 1; //打标记
l[x].cnt = l[map[head]].cnt+1;//步数+1
}
if(x == b)//剪枝1
{
printf("%d", l[x].cnt);
return 0;
}
x = map[head] - l[map[head]].k;//扩展方式2
if(x>=1 && x<=n && l[x].book == 0)
{
map[tail++] = x;//同上
l[x].book = 1;
l[x].cnt = l[map[head]].cnt+1;
}
if(x == b)//剪枝2
{
printf("%d", l[x].cnt);
return 0;
}
++head;//这个楼层扩展完毕,出队
}
if(l[b].book == 0)//若无法到达
printf("-1");
//fclose(stdin);
return 0;
}
若有不懂,可以和本蒟蒻一样,阅读《啊哈!算法》