2021寒假刷题|| 洛谷P1135 / BFS初学
文章目录

总结:
- queue队列的使用
- memset函数的使用
BFS:
- 广度优先搜索(breadth-first 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;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论