今日主题：BFS（简单的应用，复杂版大概明天更新吧，充足的睡眠不可少啊)

一.什么是BFS

\(BFS\) \((Breadth\) \(First\) \(Search\) \()\) ，即广度优先搜索（也叫做宽度优先搜索），是一种搜索策略，其原理如下图：

把你的搜索过程当作一个石头被投入水中一点一点往四周荡漾的过程，那么上面标的数字就是从石子出走到此点需要几步。

（explaned by @apple365,the IOI AKer)

二.BFS代码实现

em，只需要注意是用队列实现就行了。详细解说在代码里面。

\({\color{Springgreen}Code:}\)

int bfs(int sx,int sy){
	queue<node> q;//队列
	memset(vis,false,sizeof(vis));//清空标记数组
	vis[sx][sy]=1;//起点当然要标记，这个很重要！
	node cur={sx,sy,0};//后面的步数取决于要不要算起始格子
	q.push(cur);
	
	while(q.empty()==0){//队列不为空
		cur=q.front();
		q.pop();//取队首
		if(cur.x==bx&&cur.y==by){//判断是否到终点了
			return cur.step;//到了的话返回当前步数
		}
		
		for(int i=0;i<4;i++){//没到的话就来枚举下一步走上下左右哪个方向
			int nx=cur.x+dx[i],ny=cur.y+dy[i];//更新坐标
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='1'&&vis[nx][ny]==0){//要满足nx，ny没有出界且这个格子没有障碍物并且没有走回头路才能搜这个格子
				vis[nx][ny]=1;//标记
				node nxt={nx,ny,cur.step+1};//步数较原来的要加1
				q.push(nxt);//入队
			}
		}
	}
}

三.BFS经典例题

题单链接

基本上都是模板题，而且DFS的题都可以试着用BFS写的。

就放几道黄题吧。

1.P1746 离开中山路

模板题啊纯模板题啊，我的板子都是从这道题里面拿的（

这么简单的题为什么评黄，最多评橙好吗（

#include<bits/stdc++.h>
using namespace std;
int n,ax,ay,bx,by;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char a[1010][1010];
bool vis[1010][1010];
string s;
struct node{
	int x,y,step;
};

int bfs(int sx,int sy){
	queue<node> q;
	memset(vis,false,sizeof(vis));
	vis[sx][sy]=1;
	node cur={sx,sy,0};
	q.push(cur);
	
	while(q.empty()==0){
		cur=q.front();
		q.pop();
		if(cur.x==bx&&cur.y==by){
			return cur.step;
		}
		
		for(int i=0;i<4;i++){
			int nx=cur.x+dx[i],ny=cur.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='1'&&vis[nx][ny]==0){
				vis[nx][ny]=1;
				node nxt={nx,ny,cur.step+1};
				q.push(nxt);
			}
		}
	}
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=0;j<s.length();j++){
			a[i][j+1]=s[j];
		}
	}
	cin>>ax>>ay>>bx>>by;
	
	cout<<bfs(ax,ay);
	return 0;
}

2.P1135 奇怪的电梯

就是把二维变成了一维而已啊，基本上没有什么区别，恶意评分吧这（

#include<bits/stdc++.h>
using namespace std;
int n,a,b,k[210];
int d[]={1,-1};
bool vis[210];
struct node{
	int f,step;
};

int bfs(int nw){
	queue<node> q;
	memset(vis,false,sizeof(vis));
	vis[nw]=1;
	node cur={nw,0};
	q.push(cur);
	
	while(q.empty()==0){
		cur=q.front();
		q.pop();
		if(cur.f==b){
			return cur.step;
		}
		
		for(int i=0;i<2;i++){
			int nf=cur.f+k[cur.f]*d[i];//
			if(nf>=1&&nf<=n&&vis[nf]==0){
				vis[nf]=1;
				node nxt={nf,cur.step+1};
				q.push(nxt);
			}
		}
	}
	return -1;
}

int main() {
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	
	cout<<bfs(a);
	return 0;
}

3.P1747 好奇怪的游戏

多了几种走法而已啦，不难不难，上代码！

#include<bits/stdc++.h>
using namespace std;
int ax,ay,bx,by,n=20,ans1,ans2;
int dx[]={2,1,-1,-2,-2,-1,1,2,-2,-2,2,2};
int dy[]={1,2,2,1,-1,-2,-2,-1,2,-2,2,-2};
bool vis[30][30];
struct node{
	int x,y,step;
};

int bfs(int sx,int sy){
	bool f=0,s=0;
	queue<node> q;
	memset(vis,false,sizeof(vis));
	vis[sx][sy]=1;
	node cur={sx,sy,0};
	q.push(cur);
	
	while(q.empty()==0){
		cur=q.front();
		q.pop();
		if(cur.x==ax&&cur.y==ay&&f==0){
			ans1=cur.step;
			f=1;
		}
		if(cur.x==bx&&cur.y==by&&s==0){
			ans2=cur.step;
			s=1;
		}
		
		for(int i=0;i<12;i++){
			int nx=cur.x+dx[i],ny=cur.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==0){
				vis[nx][ny]=1;
				node nxt={nx,ny,cur.step+1};
				q.push(nxt);
			}
		}
	}
}

int main() {
	cin>>ax>>ay>>bx>>by;
	bfs(1,1);
	cout<<ans1<<"\n"<<ans2;
	return 0;
}

ybt上面的题到时候再开一个写吧（