【新知识】队列&bfs【洛谷p1996约瑟夫问题&洛谷p1451求细胞数量】

（是时候为五一培训准备真正的技术了qwq）

part1  队列(FIFO)

算法简介：

FIFO：First In First Out（先进先出）

队列是限定在一端进行插入，另一端进行删除的特殊线性表。

允许出队的一头叫做队头（head||front），允许出队的一端称为队尾（rear||tail）所有需要进队的数据项，只能从队尾进入，队列中的数据只能从队头离去qwq。

---

今天wz_小姐姐讲惹一小时滴不知道有什么用滴东西qwq，这里做个笔记吧ヽ(•̀ω•́ )ゝ

1.队列在c语言中的语法？

No.1头文件：#include<queue>

No.2统统搞一块了不管了qwq：

成员函数：

搞到一个神奇的代码qwq：

#include <queue>

#include <iostream>

using namespace std;

int main()

{

       queue<int> myQ; //疑似定义了一个队列q

       for(int i=; i<; i++) {

            myQ.push(i);//把0~9入队

            cout<<"myQ size is: "<<myQ.size()<<endl;//输出i这个元素入队之后队列的长度

       }

       for(int i=; i<myQ.size(); i++) {

          cout <<"the first:"<< myQ.front()<<endl; //输出第一个数

          myQ.pop(); //删掉第一个数（队列的长度减小了）

          cout<<"wz is little sister:"<<myQ.size()<<endl; //证明它确实减小了 彩蛋qwq

       }

       cout<<"this is amazing!"<<endl;

       return ;

}

另外还有栈：stack？？头文件的话就是#include<stack>

用法和queue差不多，请自行百度qwq

---

例题【洛谷p1996约瑟夫问题】（粉粉嫩嫩的好看qwq

算法标签：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int n,m,p=,k=;

int a[];

int main()

{

    scanf("%d%d",&n,&m);

    int j=n;

    for(int i=;i<n;i++)a[i]=i+;

    a[n]=;

    while(p<n){

        while(k<m){

            printf("%d a w i k o z i %d\n",j,a[j]);

            j=a[j];k++;//为了方便理解，这里加了两句输出

            printf("%d a y i k o y i %d\n",j,a[j]);

            puts("-------------------");

        }

        printf("我是答案qwq:%d\n",a[j]);p++;

        a[j]=a[a[j]];k=;

    }

    return ;

}
 

---

写在bfs之前：

关于lower_bound和upper_bound：

这个神奇的东西一直只是见过，咋用完全不会之前，所以今天wz跟我们讲（xian）题（che）时候顺（zhuang）带（bi）的讲了一下。

写在语法之前：头文件：#include<algorithm>（某些人疑似叫它阿拉狗日thm）

lower_bound和upper_bound都是在sort过以后使用的，（要不然用它没有意义啊qwq

1.语法：

lower_bound(a+1,a+n+1,r)①//表示在数组a中从a[1]位置到a[n]位置找到第一个大于或等于r的数，返回该数的地址

upper_bound(a+1,a+n+1,r)②//表示在数组a中从a[1]位置到a[n]位置找到第一个大于r的数，返回该数的地址

如何用lower_bound和upper_bound判断数r在某个部分（用部分吧，用数组不是很严谨qwq）是否存在：①==②？不存在：存在（突然想写三目运算符（大概写对了吧）

求序列中有几个r：②-①；

求某个数r的下标：lower_bound(a+1,a+n+1,r)-a(no why)

行吧大致补充就end-了

---

part2 bfs（广度优先搜索）：

算法描述qwq：Breadth First Search

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。（from oi-***）

伪代码：

bfs(s) {

  q = new queue()

  q.push(s)), visited[s] = true

  while (!q.empty()) {

    u = q.pop()

    for each edge(u, v) {

      if (!visited[v]) {

        q.push(v)

        visited[v] = true

      }

    }

  }

}//from oi-**（我没直接把一本通的打上来已经不错了qwq  色号#f4f4f4

---

eg：【洛谷p1451求细胞数量】

算法标签（显然搜索）：

（你猜它来自哪pulapula懒死算了qwq

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

using namespace std;

char s[];

int n,m,ans=;

bool pan[][];

int dx[]={,,,-,};

int dy[]={,,,,-};

void bfs(int a,int b){

    int h[][],x,y;

    int t=,w=;

    ans++;pan[a][b]=;

    h[][]=a;h[][]=b;

    do{

        t++;//丢掉了qwq

        for(int i=;i<=;i++){

            x=h[t][]+dx[i];

            y=h[t][]+dy[i];

            if((pan[x][y])&&(x<=n)&&(y<=m)&&(x>)&&(y>))

            {

                w++;

                h[w][]=x;

                h[w][]=y;

                pan[x][y]=;

            }

        }

    }while(t<w);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

        pan[i][j]=;

    for(int i=;i<=n;i++){

        scanf("%s",s);

        for(int j=;j<m;j++){//字符数组从零开始啊喂qwq

            if(s[j]=='')pan[i][j+]=;//从j零开始的话要加1呢qwq

        }

    }

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

        if(pan[i][j]) bfs(i,j);

    printf("%d",ans);

}

大概可能没啥了吧qwq？？？

end-

【新知识】队列&bfs【洛谷p1996约瑟夫问题&洛谷p1451求细胞数量】的相关教程结束。