#创作计划#浅（吗？）谈BFS =）

复仇者_ドラゴンコア

2024-08-01 10:32:18

发布于：浙江

41阅读

0回复

0点赞

BFS篇~

鲁迅AC比狗还狗曾经说过：这个东东好用爱用 because不用回溯它第一次就能搜到最优解

其实从上面来看就可以看出BFS的一大堆优点，比如：

1	2	3	4	5	6
不用回溯	思路简单	不会TLE（butM)	最优解问题会格外简单	敲起来快	被鲁迅用过...(?)

那，这么个好东西我们该怎么整呢？学废会了又该着呢么优化呢？

FIRST 基本思想（该解释参考清华大学出版社的算法竞赛）
BFS的基本思想其实可以用一个简单的问题解释：老鼠走迷宫 （稍后会在DFS中也会用到该问题）

BFS来解决该问题是一群老鼠走迷宫，遇见一个没走过且在迷宫内的且老鼠接下来的那一步可走到的路口就会派一只/群老鼠走这个路口，直到有老鼠走到出口。如果老鼠太多，就会MLE。（DFS会TLE是因为一只老鼠走太慢了...）有点像多线程的处理方式，对吧？但实际上，程序还是以一条线不断画圆搜索的，只不过画的很快以至于像一个圆在变大。
这里也解释一下BFS为什么能像开了挂一样一次搜到最优解的，上面也说了，他是面积（圆or椭圆？）搜索的，本狗画了张图供大家理解和对比：（第一张BFS 第二张DFS）

SECOND 具体实现和优化（优化在代码里）
BFS的代码实现模版是用STL 队列来维护所搜的点从第一个点录入队列后不断地通过方向，边界，剪枝来录入新的点，当当前点符合条件就输出并结束函数，当队列为空时代表所有可搜的点都搜完了，接下来要么输出步数，要么输出无解（有解就不会这个时候就还没输出了啊喂！）。代码如下：

#include<bits/stdc++.h>
using namespace std;
//地图，边界，方向，标记....
struct node
{
    int x;
    int y;//点的坐标
    int step;//可能的步数
    bool zhuangtai;.//可能的特殊性质（药水？传送器？）
}；
void bfs(node q//大括号~（我竟然前后呼应了！）)
{
    queue<node> a;//维护的队列
    a.push(q);
    vis[q.x][q.y]=1;//这里可标可不标，如果这里标了那就在邻居入队的时候再标一次，或者再搜素中取队头时标，这样只用标一次
    while(a.size()//队列为空时结束)//开搜~
  ｛
       node now=a.front();//取队头
       if(符合条件)
       ｛
            cout or ans=...//总结
        ｝
       vis...//标记且只用标一次
       for(int i=0;i<4;i++//一般的四个方向 but 可以写推理后更好的方向)
      ｛
            int nx=...,ny=...;//邻居
            if(剪枝+边界+能走)
           ｛
                    a.push();//舒适的入队but记得步数加一，状态要变，有传送门要录多个点等...
            ｝
       ｝
   ｝
    cout<<"没有答案嘤嘤嘤"；//见上
    return;
}
int main()
{
    cin>>....//输入部分
    n--,m--,...//可能的数据处理，比如题目数据从一开始but你和你的数组是从零开始的
    bfs({x,y})//可能的特殊开始点（当然一般是0,0）大括号的作用是可以在bfs函数在编辑的时候形参可以直接写node
    cout<<ans;//答案在ans里？（一般可以在bfs里输出，随你）
}