关于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;
}