关于c++:2021寒假刷题-洛谷P1135-BFS初学

总结:

• 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;
}