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