总结:
- queue 队列的应用
- memeset 函数的应用
-
BFS:
- 广度优先搜寻(breadth-fifirst searching,bfs),尽量广阔地搜寻,在每一步优先拜访间隔最近的结点。
- 因为 BFS 须要依照 接触到的程序 来拜访,所以须要一种 先入先出 的数据结构——队列来辅助实现。
- 当咱们搜寻一个结点时,将它 所有的分支 推入队列;解决完以后结点后,再从队列头取出 下一个结点 持续进行搜寻。
#include<bits/stdc++.h>
using namespace std;
/*
思路:5 1 5
楼层:1 2 3 4 5
按钮:3 3 1 2 5
将楼层 A 压入队列中,而后找非法的上下楼 压入队列
一直出队 入队 直到 B 出队就找到了
*/
const int MAXN = 205;
int flr[MAXN]; // 存储按钮
int dis[MAXN];// 寄存按按钮次数
int main(){
int n,a,b;
cin>>n>>a>>b;
for(int i = 1;i<=n;i++){cin>>flr[i];
}
memset(dis,-1,sizeof(dis));
//memset 函数初始化只能是: 0,-1 ,0x3f
dis[a]= 0;
queue<int> q;// 创立队列, int 类型
q.push(a); // 把 a 压入队列
while(!q.empty()){ // 判断是否非空
int x = q.front(); // 取第一个值,front 只是返回这个值, 并没有把这个值入列
q.pop(); // 出列
if(x == b){cout<<dis[x]<<endl;
return 0; // 这里没有写 break; 输出后果之后间接完结了, 间接 return 0 即可
}
int y; // 下一步达到的楼层
y = x-flr[x];
if(y>0 && dis[y]==-1){ // 要判断这个楼层之前没有拜访过, 不然会反复拜访
dis[y] = dis[x]+1; // 达到 y 层须要的按键次数
q.push(y); // 达到了之后要把 y 入队 持续下一轮的判断
}
y = x+flr[x];
if(y<=n && dis[y]==-1){dis[y] = dis[x]+1;
q.push(y);
}
}
cout<<-1<<endl;
}