广度优先搜索BFS
广度优先搜索BFS
广度优先搜索（以下简称BFS)是搜索技术中常用的一种搜索。
BFS体现在广度一词上，一层一层进行遍历，常见的有在矩阵（二维数组）上的遍历以及树和图的遍历。体现在二维数组的遍历顺序如下（假设起点在左上），在只能上下左右四个方向遍历时，序号代表遍历顺序。
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
| 4 | 5 | 6 | 7 |
序号相同的位置访问顺序可任意。实现时，当访问1号位置时，就要对两个2号位置进行标记（我要准备访问你了），当访问任一个2号位置时就要标记它能访问到的3号位置，依次类推。
实现：对于一层一层遍历的结构，我们使用队列queue这一先进先出的数据结构。
首先1入队，遍历与1相邻的位置，即两个2入队，然后1出队，然后遍历与队尾2相邻的位置，将其入队（此时还有一个2号位置没遍历，但是不用担心，刚入队的3号位置在队首，不会影响层层遍历的光系），队尾2出队，此时队尾仍然是2号位置，此时访问该2号位置，将与其相邻且没遍历过位置入队，此时所有的3号位置全部入队，然后该2号位置出队。依此遍历至最后。
对于树结构的遍历其实就是对数结构的层序遍历，一层一层遍历
黑色字体代表结点序号，红色字体为遍历层序。
首先遍历根结点，然后还是两个2号根结点的叶子结点入队遍历方式与矩阵相似。
图结构的遍历也类似
//模板
int v[Max][Max];//标记数组，标记某位置是否已经访问
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct A
{
int x,y,t;//x,y表示位置坐标，t表示遍历序号（依题而异），
}root,top;//结构体表示每一个位置
void bfs(int x,int y)//x,y传入起始位置坐标
{
root.x=x;
root.y=y;
root.t=0;
queue<A>Q;
Q.push(root);//起始位置入队
v[x][y]=1;//标记起始位置已经访问
while(!Q.empty())
{
top=Q.front();
Q.pop();
v[top.x][top.y]=1;
for(int i=0;i<4;i++)//遍历当前访问结点相邻结点
{
int nx=top.x+dx[i];
int ny=top.y+dy[i];
int nt=top.t+1;//与当前访问结点相邻点访问序号+1
if(nx<1||nx>n||ny<1||ny>m) continue;//约束，防止数组越界
ans[nx][ny]=nt;//记录每个位置的访问序号，依题而异
if(...){}
if(!v[nx][ny])//未被访问，入队等待访问
{
root.x=nx;
root.y=ny;
root.t=nt;
Q.push(root);
v[nx][ny]=1;
}
}
}
}例题：
力扣1293：
网格中的最短路径
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
输入1：
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
输出2：6
输入2：
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
输出2：-1
来源：力扣（LeetCode）
原题链接
思考：
思路自然是深搜，值得注意的是如果v数组跟平常一样只设置二维，可能从一条路径经过i,j这个点出不去，而此时v[i][j]被标记为访问过，可能正确答案包含的路径却偏偏包含i,j这个点，这就无法得到正确答案咯；这时我们可以开一个三维v数组，表示每次经过该点时经过的障碍点的次数。
AC代码：
class Solution {
public:
struct A
{
int x,y,k,ans;
}root,top;
int n,m,K;
int ans=10000;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int a[100][100];
bool v[50][50][1600];
void bfs()
{
root.x=0;
root.y=0;
root.k=K;
root.ans=0;
v[0][0][K]=1;
queue<A>Q;
Q.push(root);
while(!Q.empty())
{
top=Q.front();
Q.pop();
if(top.k<0) continue;
v[top.x][top.y][top.k]=1;
for(int i=0;i<4;i++)
{
int nx=top.x+dx[i];
int ny=top.y+dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(a[nx][ny]==1&&top.k<1) continue;
if(nx==n-1&&ny==m-1)
{
ans=min(ans,top.ans+1);
}
if(!v[nx][ny][top.k])
{
root.x=nx;
root.y=ny;
root.ans=top.ans+1;
if(a[nx][ny]==1) root.k=top.k-1;
else root.k=top.k;
Q.push(root);
v[nx][ny][top.k]=1;
}
}
}
}
int shortestPath(vector<vector<int>>& grid, int k) {
K=k;
n=grid.size();
m=grid[0].size();
if(n==1&&m==1) return 0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
a[i][j]=grid[i][j];
bfs();
if(ans!=10000) return ans;
return -1;
return ans;
}
};多个原始点的搜索：
洛谷p1332
军团是一个n 行m 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直
到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给
巫妖王，以便对血色先锋军进行一轮有针对性的围剿.
输入描述：
第一行：n,m,a,b;表示军团矩阵有n 行m 列。有 a 个感染源，b 为血色敢死队中领主的数量。
接下来a行：每行有两个整数x,y,表示感染源再第x行第y列。
接下来b行:每行两个整数x,y,表示领主的位置再第x行第y列。
输出描述：
第1行至第b行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。
如果某个人的位置在感染原，那么他感染瘟疫的时间为0；
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int Max=5e2+20;
inline int read()
{
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}
while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}
while(ch>='0'&&ch<='9');return x*f;
}
struct A
{
int x,y,t;
}root,top;
int n,m;
int ans[Max][Max];
int p[100000][3];
bool v[Max][Max];
queue<A>Q;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs()
{
while(!Q.empty())
{
top=Q.front();
Q.pop();
v[top.x][top.y]=1;
for(int i=0;i<4;i++)
{
int nx=top.x+dx[i];
int ny=top.y+dy[i];
int nt=top.t+1;
if(nx<1||nx>n||ny<1||ny>m||v[nx][ny]) continue;
ans[nx][ny]=nt;
root.x=nx;
root.y=ny;
root.t=nt;
Q.push(root);
v[nx][ny]=1;
}
}
}
int main()
{
n=read(),m=read();
int a=read(),b=read();
for(int i=1;i<=a;i++)
{
root.x=read(),root.y=read();
Q.push(root);//按顺序提前将搜索原点入队
v[root.x][root.y]=1;//标记已经访问，防止别的搜索点访问搜索起点。
}
for(int i=1;i<=b;i++)
{
p[i][1]=read(),p[i][2]=read();//记录领主的位置
}
bfs();
for(int i=1;i<=b;i++)
{
printf("%d\n",ans[p[i][1]][p[i][2]]);
}
return 0;
}