原题链接
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼$(1 \le i \le N)$ 上有一个数字 $K_i(0 \le K_i \le N)$。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3 ,1 ,2 ,5$ 代表了$K_i(K_1=3,K_2=3,…)$，从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？
输入输出格式
输入格式
共二行。
第一行为 $3$ 个用空格隔开的正整数，表示 $N,A,B(1≤N≤200, 1≤A,B≤N)$。
第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。
输出格式
一行，即最少按键次数,若无法到达，则输出 $−1$。
输入输出样例
输入1 :
输出1 :
解法（bfs）
一道很简单的 bfs 裸题，根据题意可知，每一层至多有两种情况，向上或者向下当前层数，既然要求最少按几次按钮当然是用 bfs。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <bits/stdc++.h>
using namespace std;
struct Node
{
int f,step;
};
inline int read()
{
char ch=getchar();int ret=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
return ret*f;
}
queue<Node> q;
int n=read(),a=read(),b=read(),p[205],book[100005];
Node t;
const int d[]={-1,1};
int main()
{
memset(book,-1,sizeof(book));
for(int i=1;i<=n;i++)
p[i]=read();
Node t1;
t1.f=a;
t1.step=0;
book[a]=0;
q.push(t1);
while(!q.empty())
{
t=q.front();
q.pop();
if(t.f==b)
break;
for(int i=0;i<2;i++)
{
int tf;
if(d[i]==1)
tf=t.f+p[t.f];
else
tf=t.f-p[t.f];
if(tf<1||tf>n||book[tf]==1)
continue;
book[tf]=1;
Node t2;
t2.f=tf;
t2.step=t.step+1;
q.push(t2);
}
}
if(t.f==b)
printf("%d",t.step);
else
printf("-1");
return 0;
}
|
