一、算法内容

1.简介

广度优先搜索BFS（Breadth First Search）按照广度优先的方式进行搜索，可以理解为“尝试所有下一步可能”地穷举所有可行的方案，并不断尝试，直到找到一种情况满足问题问题的要求。

BFS从起点开始，优先搜索离起点最近的点，然后由这个最近的点扩展其他稍近的点，这样一层一层的扩展，就像水波扩散一样。故而可以把BFS当成并行计算的一种模拟。

广度优先搜索可以用队列实现，而且几乎都是用队列实现，所以要学会广度优先搜索，首先必须要学会队列。而在BFS中，可能不止使用基本的队列，优先队列和双端队列也可能被使用并用来优化BFS。在后续BFS优化的学习中，我们会提到这些知识。

2.与DFS的对比

与深度优先搜索不同的是，广度优先搜索会先将与起始点距离较近的点搜索完毕，再继续搜索较远的点，而深搜却是沿着一个分支搜到最后。故而当需要选择搜索方式的时候，评估答案可能出现的位置将作为一个可靠的依据。如果答案出现在浅层，那么使用BFS更好；如果答案出现在深层，那么使用DFS更好。

如果将搜索的过程画出来，那么它就像一棵树，每一个结点都有相应的状态，分别代表了一种可能性。之所以叫做广度优先，是因为我们总是将当前层拓展完之后才会进入树的下一层。

3.队列使用的基本过程

BFS需要借助队列来实现：

1. 初始的时候把起始点放到队列中，并标记起点访问。
2. 如果队列不为空，从队列中取出一个元素u，否则算法结束。
3. 访问和u相连的所有点v，如果v没有被访问，把v入队，并标记已经访问。
4. 重复执行步骤 2。

二、算法实现

1.算法模板

参数 bfs(变量)
{起点设置将起点入队如果队列不为空:取出队首:枚举此时下一步所有的可能性：得到下一步的状态如果下一步是合法的/更优的：将下一步的状态入队返回答案
}

2.实例剖析：T1770 洪水

（1）限定条件

• 水不能流出矩阵，即任何时候，当前坐标$(x,y)$满足$1\le x\le n,1\le y\le m$。
• 水往低处流，即水要向高度相同或者更低的地方扩散。
• 注意不要原路返回，否则将进入无限循环。

（2）更新状态

若当前坐标为$(x,y)$，则下一步的坐标即为$(x-1,y),(x+1,y),(x,y-1),(x,y+1)$。我们需要在限定条件内走到这些位置。

而我们的状态分为两部分构成，结合这两个状态我们就可以唯一标识一种情况：

• 第一部分：显然我们当前的坐标是我们的一个状态。
• 第二部分：为了保证我们不要进入循环，我们需要标记我们的来路，这就是第二部分的状态。

（3）正解代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib> 
#include <cmath>
#include <queue>using namespace std;
typedef long long ll;
struct node
{ll x,y;
};
ll dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
ll mp[1010][1010];
bool vis[1010][1010];
ll n,m,ans;
void bfs(ll sx,ll sy)
{queue<node> q;q.push(node{sx,sy});vis[sx][sy]=true;ans++;while(!q.empty()){node now=q.front();q.pop();for(ll i=0;i<4;i++){node New;New.x=now.x+dx[i];New.y=now.y+dy[i];if(New.x>=1 && New.x<=n && New.y>=1 && New.y<=m && !vis[New.x][New.y] && mp[New.x][New.y]<=mp[now.x][now.y]){vis[New.x][New.y]=true;ans++;q.push(New);}}}
}
int main()
{cin>>n>>m;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)cin>>mp[i][j];ll sx,sy;cin>>sx>>sy;bfs(sx,sy);cout<<n*m-ans<<endl;return 0;
} 

三、作业

1.橙题

P1162 填涂颜色

T1770 洪水

2.黄题

P1443 马的遍历

P1649 [USACO07OCT]Obstacle Course S

P4017 最大食物链计数