TIP
最近在做关于广度优先搜索的题，平常接触关于深度优先搜索的题比较多一点，遇到bfs不知道该怎么下手了，所以就特意练了两天，有了一点处理的小想法，记录下来，免得以后忘记了。
# 写在前面
做题期间才明白，为什么广度优先搜索是一个队列，特别是在做关于图的搜索的时候，有几个方向都可以走，如何找到到达某一个点的最短路径，把一个点（也就是当前所要操作的点）能一步操作就可以到达的点入队，所以上一个点到达下一个点只相差1，可以采用迭代的方式记录步数，并且求出的解也一定会是一个最优解。
关于广度优先搜索的题型一般有两个主要特征：①求最优解；②一个元素会有很多种处理方式。万变不离其宗，只要看到这道题有这两个主要特征，那么这就是一个bfs类型的题，距离解决问题也就不远了，有时候却也不是这样，因为部分情况下在搜索的过程中，有些数据处理也稍复杂，往往并不是不会搜索，而是中间的一些数据不知道怎么处理，要么就是太慢 通过不了测试点。
做这样类型的题首先要选择好合适的存储方式，然后建一个队列，先将起始点加入到队列之中，然后调用bfs()，当队列不为空的时候，就可以进行操作。取出队头元素，对队头元素进行处理，如果可以走到下一个点，就将这个点加入到队列之中，加上题中要求所必须的操作，知道队列为空的时候才结束，此时应该所有想实现的操作都已经完成，否则就是应该有bug了。
//首先把起始点入队
bfs();
{
while(s.size()){
取出队列的头元素;
类型 x = s.front();
s.pop();
for(int i=0;i<n;i++){
所要操作的方法;
一些处理的方法，满足条件就要加入到队列之中;
s.push(元素);
}
}
}
这个大概就是bfs()里的模板。
# 就题而论
接下来就来看看几道题吧。
# 填涂颜色（洛谷P1162）
题目描述
由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
输入格式
每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30) 接下来nn行，由00和11组成的n \times nn×n的方阵。 方阵内只有一个闭合圈，圈内至少有一个00。
输出格式
已经填好数字22的完整方阵。
# 思路分析
这道题我们该怎么去做呢？这个方阵中只有两种状态，一种是0，一种是1，并且方阵中只有一个闭合圈，那么我们如果想找到哪些0在闭合圈之中是不好找的，但是我们却可以很容易找到哪些0不在闭合圈之中，在边界中找0，如果在边界中找不到0就说明1占领了整个边界，所以我们以边界0作为起始点，往方阵的内部去搜索，如果遇到了1就要终止，没有遇到1就可以往四个方向走，直到所有的点都走一遍。
我是这么想的，先把方阵中所有的0都转换为2，然后从四个边界开始搜索2，以2开始作为起始点，运用dfs或者bfs进行搜索，将圈外的2全部变为0然后就结束了。
# 代码
dfs版本
#include<iostream>
using namespace std;
int a[32][32];
int b[4][2]= {0,1,0,-1,1,0,-1,0};
int n;
void dfs(int x,int y) {
if(x<0||y<0||x>n-1||y>n-1||a[x][y]==1||a[x][y]==0) {
return;
}
if(a[x][y]==2) {
a[x][y]=0;
}
for(int i=0; i<4; i++) {
dfs(x-b[i][0],y-b[i][1]);
}
}
int main() {
cin >> n;
for(int i=0 ; i < n; i++) {
for(int j=0; j < n; j++) {
cin >> a[i][j];
if(a[i][j]==0) {
a[i][j]=2;
}
}
}
for(int k=0; k<n; k++) {
if(a[k][0]==2) {
dfs(k,0);
}
}
for(int k=0; k<n; k++) {
if(a[0][k]==2) {
dfs(0,k);
}
}
for(int k=0; k<n; k++) {
if(a[k][n-1]==2) {
dfs(k,n-1);
}
}
for(int k=0; k<n; k++) {
if(a[n-1][k]) {
dfs(n-1,k);
}
}
for(int i=0 ; i < n; i++) {
for(int j=0; j < n; j++) {
cout << a[i][j] << ' ';
}
if(i!=n-1){
cout << endl;
}
}
return 0;
}
bfs版本
#include<iostream>
#include<queue>
using namespace std;
int a[32][32];
int b[4][2]= {0,1,0,-1,1,0,-1,0};
int n;
struct Node
{
int ax;
int ay;
};
queue<Node> s;
bool isok(int x,int y)
{
if(x<0||y<0||x>n-1||y>n-1||a[x][y]==1||a[x][y]==0) {
return false;
}
return true;
}
void bfs(int x,int y) {
while(s.size()){
Node E=s.front();
x=E.ax;
y=E.ay;
s.pop();
for(int i=0; i<4; i++) {
if(isok(x-b[i][0],y-b[i][1])){
a[x-b[i][0]][y-b[i][1]]=0;
s.push((Node){x-b[i][0],y-b[i][1]});
}
}
}
}
int main() {
cin >> n;
for(int i=0 ; i < n; i++) {
for(int j=0; j < n; j++) {
cin >> a[i][j];
if(a[i][j]==0) {
a[i][j]=2;
}
}
}
for(int k=0; k<n; k++) {
if(a[k][0]==2) {
s.push((Node){k,0});
a[k][0]=0;
bfs(k,0);
}
}
for(int k=0; k<n; k++) {
if(a[0][k]==2) {
s.push((Node){0,k});
a[0][k]=0;
bfs(0,k);
}
}
for(int k=0; k<n; k++) {
if(a[k][n-1]==2) {
s.push((Node){k,n-1});
a[k][n-1]=0;
bfs(k,n-1);
}
}
for(int k=0; k<n; k++) {
if(a[n-1][k]==2) {
s.push((Node){n-1,k});
a[n-1][k]=0;
bfs(n-1,k);
}
}
for(int i=0 ; i < n; i++) {
for(int j=0; j < n; j++) {
cout << a[i][j] << ' ';
}
if(i!=n-1){
cout << endl;
}
}
return 0;
}
# 马的遍历
题目描述（洛谷P1443）
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据，棋盘的大小和马的坐标
输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
# 思路分析
这道题是以象棋棋盘为背景的一道题，前提你要知道马要怎么走，马走日，所以就会有八个方向走可以（-1,-2）,（-2,-1）,（1,-2）,（2,-1）,（2,1）,（1,2）,（-1,2）,（-2,1），那么有了可以走的方向就好弄了，只需要每个点都尝试一下这八个方向都能不能走就可以了，然后还要求起始点到达每个点的最少要走几步，我们可以采用二维数组的存储方式，将数组初始化为-1，因为当一个点不能够到达的时候，就是-1，马每走到一个点都是一个最短路径，已经走过的点就不能再走了，因为已经是最优的了。 怎么记录当前走的是第几步，其实这也很好弄，马所走的下一个点所需要的步数就等于走到当前点所需要的步数+1。
# 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;//棋盘大小
int x,y;//马的坐标
int dir[8][2]= {-1,-2,-2,-1,1,-2,2,-1,2,1,1,2,-1,2,-2,1};
int a[402][402];//棋盘
bool vis[402][402];//标记当前点有没有被走过
struct Node {
int ax;//横坐标
int ay;//纵坐标
};
queue<Node> s;
void init() {
// for(int i=0;i<n;i++){
// fill(vis[i],vis[i]+m+1,false);
// fill(a[i],a[i]+m+1,-1);//初始化
// }
s.push((Node) {
x,y
});//将起始点加入到队列之中
vis[x][y]=true;//标记已经走过
a[x][y]=0;//自身为0
}
bool isok(int x,int y) {
if(vis[x][y]) { //假如被走过
return false;
}
if(x<1||y<1||x>n||y>m) { //假如越界
return false;
}
return true;
}
void bfs(int x,int y) {
while(s.size()) { //当队列不为空的时候
Node E=s.front();//取队头元素
s.pop();//队头出队列
Node e;//尝试所走的点
for(int i=0; i<8; i++) {
e.ax=E.ax+dir[i][0];
e.ay=E.ay+dir[i][1];
if(isok(e.ax,e.ay)){
s.push(e);//一步可以到达的点加入到队列之中
vis[e.ax][e.ay]=true;//标记被走过
a[e.ax][e.ay]=a[E.ax][E.ay]+1;//记录步数
}
}
}
}
int main() {
cin >> n >> m >> x >> y;
init();
bfs(x,y);
for(int i=1; i<=n; i++) { //输出结果
for(int j=1; j<=m; j++) {
printf("%-5d",a[i][j]);
}
cout << endl;
}
return 0;
}