题目链接:https://www.luogu.org/problemnew/show/P1135
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 i 层楼 (1≤i≤N) 上有一个数字Ki(0≤Ki≤N) 。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3,3,1,2,5 代表了Ki(K1=3,K2=3,…) ,从 1 楼开始。在 1楼,按“上”可以到 4 楼,按“下”是不起作用的,因为没有 −2 楼。那么,从 A 楼到 B 楼至少要按几次按钮呢?
输入格式:
共二行。
第一行为 3 个用空格隔开的正整数,表示N,A,B(1≤N≤200,1≤A,B≤N) 。
第二行为 N 个用空格隔开的非负整数,表示Ki 。
输出格式:
一行,即最少按键次数,若无法到达,则输出 −1 。
输入样例#1:
5 1 5
3 3 1 2 5
输出样例#1:
3裸的bfs
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, a, b;
struct node
{
int x, step;
};
int arr[];
int vis[];
queue<node>q;int bfs()
{
node now, next;
while (!q.empty())
{
now = q.front();
q.pop();
if (now.x == b)
{
return now.step;
}
if (now.x + arr[now.x] <= && !vis[now.x + arr[now.x]]) //向上坐电梯
{
next.x = now.x + arr[now.x];
vis[next.x] = ;
next.step=now.step+;
q.push(next);
}
if (now.x - arr[now.x] >= && !vis[now.x - arr[now.x]]) //向下坐电梯
{
next.x = now.x - arr[now.x];
vis[next.x] = ;
next.step = now.step + ;
q.push(next);
}
}
return -;
}int main()
{
cin >> n >> a >> b;
memset(vis, , sizeof(vis));
for (int i = ; i <= n; i++)
scanf("%d", &arr[i]);
node now; now.x =a , now.step = ;
q.push(now);
int ans=bfs();
cout << ans << endl;
return ;
}
2018-05-31