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;
}