迅达电梯300P溜车，广度优先搜索——奇怪的电梯(洛谷 P1135)

广度优先搜索普及/提高篇，今天讲述的是洛谷里的一道题 奇怪的电梯(洛谷 P1135)

迅达电梯300P溜车、说一下我解题时候的思路吧。

首先读清楚题目，题目要求输出从 a楼 到 b楼的最少次数，楼层必须在[1,n]之间升降。

这种求一种最短的结果，优先采用BSF比DFS效率更高。

对于电梯的一层，我们可以建立一个结构体，保存它当前是第几层楼，可以+-几层楼（注意，这里是+-几层楼，而不是可以去到第几层楼），同时保留从a层到该层按下按钮的次数。

然后用book[201] 来记录一下哪些楼已经去过，其实楼层都只走一遍，无论最小次数怎么走，一定不走之前走过的楼。

然后就是利用队列(queue)，套用最基本的BFS模板即可。

这里不用遍历多个方向，只有往上和往下，两个if就可以了。

题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第ii层楼(1≤i≤N)(1≤i≤N)上有一个数字Ki(0≤Ki≤N)Ki​(0≤Ki​≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3,3,1,2,53,3,1,2,5代表了Ki(K1=3,K2=3,…)Ki​(K1​=3,K2​=3,…)，从11楼开始。在11楼，按“上”可以到44楼，按“下”是不起作用的，因为没有−2−2楼。那么，从AA楼到BB楼至少要按几次按钮呢？

输入格式
共二行。

第一行为33个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。

第二行为NN个用空格隔开的非负整数，表示KiKi​。

输出格式
一行，即最少按键次数,若无法到达，则输出−1−1。

输入输出样例

输入 #1

5 1 5
3 3 1 2 5

输出 #1

3

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
struct lou{int now; //代表当前所在楼层int arr; //代表可以+-的楼层数int steps;
}lc[201];
int book[201],n,a,b;
queue<lou> q;
void bfs(){lc[a].steps=0; book[a]=1;q.push(lc[a]);while(!q.empty()){lou f = q.front();if(f.now == b){cout<<f.steps;break;}if(f.now+f.arr>=1&&f.now+f.arr<=b && book[f.now+f.arr]==0){lc[f.now+f.arr].steps = f.steps + 1;q.push(lc[f.now+f.arr]); book[f.now+f.arr]=1;}if(f.now-f.arr>=1&&f.now-f.arr<=b && book[f.now-f.arr]==0){lc[f.now-f.arr].steps = f.steps + 1;q.push(lc[f.now-f.arr]); book[f.now-f.arr]=1;}q.pop();}if(q.empty()) cout<<"-1";
}
int main() {cin>>n>>a>>b;for(int i=1;i<=n;i++){lc[i].now = i;cin>>lc[i].arr;}bfs();return 0;
}