奇怪的电梯

题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤N)上有一个数字Ki(0≤Ki ≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,5代表了Ki(K1=3,K2=3,…)，从1楼开始始。在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有−2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入格式
共二行。
第一行为33个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)
第二行为NN个用空格隔开的非负整数，表示Ki。
输出格式
一行，即最少按键次数,若无法到达，则输出−1。
输入输出样例
输入
5 1 5
3 3 1 2 5
输出
3

分析
这题是一道简单的搜索题
我用了两种方法，深搜和广搜
AC代码
1.深搜
有三种情况
1.不坐电梯
2.坐电梯上楼
3.坐电梯下楼
每种情况搜下去，注意判断重复，否则会死循环

#include<iostream>
#include<algorithm>
using namespace std;
int n,a,b,s,f[205],c[205];
void dfs(int x,int sum)
{
   
	if(x==b){
   s=min(s,sum);return;}//找最小
	if(sum>=s)return;//最优化剪枝
	c[x]=1;//搜过
	if(x+f[x]<=n)if(!c[x+f[x]])dfs(x+f[x],sum+1);//上楼
	if(x-f[x]>=1)if(!c[x-f[x]])dfs(x-f[x],sum+1);//下楼
	c[x]=0;//回溯
}
int main()
{
   
	s=2147483647;//最大值
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)cin>>f[i];
	dfs(a,0);//初值
	if(s==2147483647)cout<<-1;//如果找不到就输出-1
	else cout<<s;
}

2.广搜
也是三种情况
用广搜模板稍稍改一下就行了

#include<iostream>
using namespace std;
long long n,a,b,head,tail,st[205][2],c[205],f[205]; 
void bfs()
{
   
	tail=1;
	st[1][0]=a;st[1][1]=0;//初值
	c[a]=1;
	while(head<tail&&!c[b])//避免当a等于b的情况
	{
   
		head++;
		int x=st[head][0];
	    if(x+f[x]<=n)if(!c[x+f[x]])//上楼的条件
		{
   c[x+f[x]]=1;tail++;st[tail][0]=x+f[x];st[tail][1]=st[head][1]+1;}//更新
		if(st[tail][0]==b){
   cout<<st[tail][1];break;}//记住要break，不然会和下面重复输出
	    if(x-f[x]>=1)if(!c[x-f[x]])//下楼的条件
		{
   c[x-f[x]]=1;tail++;st[tail][0]=x-f[x];st[tail][1]=st[head][1]+1;}//更新
		if(st[tail][0]==b)cout<<st[tail][1];
	}
}
int main()
{
   
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)cin>>f[i];
	bfs();
	if(a==b)cout<<0;//特判
	if(!c[b])cout<<-1;//判断是否到过这个点
}

谢谢欣赏