【bfs】奇怪的电梯

奇怪的电梯 题目描述

c大楼有一个一种很奇怪的电梯。

大楼的每一层楼都可以停电梯，而且第 i 层楼 (1≤i≤N) 上有一个数字Ki(0≤Ki≤N)。

电梯只有四个按钮：开，关，上，下。

上下的层数等于当前楼层上的那个数字。

当然，如果不能满足要求，相应的按钮就会失灵。

例如：3,3,1,2,5 代表了Ki (K1=3,K2=3,…)，在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有−2楼。

那么，从A楼到B楼至少要按几次按钮呢？
输入格式：
第一行包含3个用空格隔开的正整数，分别表示N,A,B (1≤N≤200,1≤A,B≤N) 。

第二行包含N 个用空格隔开的非负整数，表示Ki 。

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

输入样例：

5 1 5
3 3 1 2 5

输出样例

3

解题思路

利用bfs（广度优先搜索）来求解最短路问题
本题只有上下两个方向，如果是走迷宫类型一般为四个方向

代码

#include 
#include 
using namespace std;
struct floor1
{
	int x;
	int y;
}f;
queue <floor1> q;
int main()
{
	int n,a,b;
	scanf("%d %d %d",&n,&a,&b);
	int i;
	int step[205];
	int step1[205]={0};
	for(i=1;i<=n;i++)
	{
		scanf("%d",&step[i]);
	}
	floor1 f1,f2;
	f1.x=a;
	f1.y=0;
	step1[a]=1;
	q.push(f1);
	while(!q.empty())
	{
		f2=q.front();
		q.pop();
		if(f2.x==b) break;
		i=step[f2.x]+f2.x;
		if(i<=n&&!step1[i])
		{
			step1[i]=1;
			f1.x=i;
			f1.y=f2.y+1;
			q.push(f1);
		}
		i=f2.x-step[f2.x];
		if(i>=1&&!step1[i])
		{
			step1[i]=1;
			f1.x=i;
			f1.y=f2.y+1;
			q.push(f1);
		}
	}
	if(f2.x==b) printf("%d",f2.y);
	else printf("-1");
	return 0;
}

代码分析

结构体储存某一时刻的情况：楼层数（x）和按键的次数（y）

数组step用来储存楼层上的数字
数组step1用来判断是否已经到过某楼层，对已到的楼层进行标记，避免过程重复（若前后两次到达4层，在4层所能做的选择是一样的：往上或往下step[4]层，过程重复。

若不做标记且最终无法到达目标楼层，可能会陷入死循环）

f1存储起点的状态，f1.x为层数，f1.y为按键次数
将step1[a]的值变为1（之前初始化为0）来标记已到过此楼层
因接下来的循环判断条件为队列不为空，所以最开始单独将起点状态（f1）放入队列q

f2为某一时刻的状态，f1为f2作出的选择后（向上或向下）的结果，将所有选择结果存入队列q，利用队列的特性进行判断
（ps：第7行的注释应该是i<=n…）

用f2.x==b判断是否达到目标楼层