前言
BFS，英文全称Breadth First Search，也就是广度优先搜索。
DFS用递归实现节点的拓展，而BFS用队列实现节点的拓展，用来求最短步数比较方便。
这次就不按题目的顺序写了，按题目难度写吧。前四题难度依次递增，后面还有几题是上周做过的原题我就不写了(<stron>)</stron>，既然用DFS能很快地写出来，我就不写BFS解法了 （才不是我不会写BFS呢）
nefu 1700 营救-搜索
BFS入门题，用队列实现BFS即可。
优化：不需要写函数（因为不需要用递归），也不需要开vis数组标记每个点是否被访问，可以直接更改原图，把原图中已经走过的点变为墙即可。
以下，33行代码，24ms通过9个数据，成功AC。
#include <bits/stdc++.h>
using namespace std;
char a[1001][1001];
int n,beginx,beginy,endx,endy,newx,newy;
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//定义上下左右四个方向
struct node
{
int x,y,cnt;//cnt记录步数
};
queue<node>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]+1;//以1、1为起点输入二维字符数组
cin>>beginx>>beginy>>endx>>endy;
q.push({beginx,beginy,0});//先把起点入队，开始时cnt=0
while(!q.empty())//开始搜索，用队列实现BFS，当队列为空还未到终点，则无法达到终点(求最短步数实际上已经保证了一定能到终点)
{
node tmp=q.front();q.pop();//按队列顺序依次取出队首tmp
if(tmp.x==endx&&tmp.y==endy){printf("%d\n",tmp.cnt);break;}//找到终点，输出答案，搜索结束
a[tmp.x][tmp.y]='1';//原节点变为"墙"
for(int i=0;i<4;i++)//四个方向搜索，寻找可行的下一个新节点
{
newx=tmp.x+dir[i][0];
newy=tmp.y+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&a[newx][newy]=='0')
{a[newx][newy]='1';q.push({newx,newy,tmp.cnt+1});}//新节点入队，并且走到新节点的步数是原节点的步数加一
}
}
return 0;
}
nefu 1701 最少转弯问题-搜索
在结构体中加一个flag变量记录某个节点的上一个节点走的方向是上下方向还是左右方向，即可在每次搜索时判断走到某个节点时是否拐弯。
#include <bits/stdc++.h>
using namespace std;
int n,m,beginx,beginy,endx,endy,newx,newy,a[105][105];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//上、下、左、右
struct node
{
int x,y,cnt,flag;//cnt记录拐弯次数，flag记录上一个点走的方向是上下方向(记为1)或者左右方向(记为2)
};
queue<node>q;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>beginx>>beginy>>endx>>endy;
for(int i=0;i<4;i++)//先搜索起点走到下一步的方向
{
newx=beginx+dir[i][0];
newy=beginy+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]==0)
{
if(dir[i][1]==0)q.push({beginx,beginy,0,1});//起点走到下一步走的是上下方向，起点入队
else if(dir[i][0]==0) q.push({beginx,beginy,0,2});//起点走到下一步走的是左右方向，起点入队
}
}
while(!q.empty())//开始搜索，用队列实现BFS
{
node tmp=q.front();q.pop();//按队列顺序依次取出队首tmp
if(tmp.x==endx&&tmp.y==endy){printf("%d\n",tmp.cnt);break;}
a[tmp.x][tmp.y]=1;//原节点变为"墙"
for(int i=0;i<4;i++)//四个方向搜索，寻找可行的下一个新节点
{
newx=tmp.x+dir[i][0];
newy=tmp.y+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]==0)
{
if(dir[i][1]==0&&tmp.flag==2)q.push({newx,newy,tmp.cnt+1,1});//原左右方向拐弯了，tmp.cnt+1，更新为上下方向
else if(dir[i][0]==0&&tmp.flag==1) q.push({newx,newy,tmp.cnt+1,2});//原上下方向拐弯了，tmp.cnt+1，更新为左右方向
else q.push({newx,newy,tmp.cnt,tmp.flag});//其他情况未拐弯，tmp.cnt不变，tmp.flag不变
}
}
}
return 0;
}
洛谷 P1443 马的遍历
这题也不需要开vis访问标记数组，因为在搜索过程中只要能第一次走到(newx,newy)这个点，那么就已经求出了到(newx,newy)这个点的最短步数ans[newx][newy]，也就是上一个节点的步数加一。
注意一些小细节：
1、马走的是“日”字型方向，每次搜索最多能拓展8个方向
2、memset函数可以初始化数组为0或-1（不支持初始化为1）
3、左对齐五格，输出的格式是 %-5d；右对齐五格，输出的格式是 %5d
#include <bits/stdc++.h>
using namespace std;
int n,m,beginx,beginy,newx,newy,ans[401][401];
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};
struct node
{
int x,y,cnt;//cnt记录步数
};
queue<node>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>beginx>>beginy;
memset(ans,-1,sizeof(ans));//初始化答案数组为-1
q.push({beginx,beginy,0});//先把起点入队，开始时cnt=0
ans[beginx][beginy]=0;//初始点步数为0
while(!q.empty())//开始搜索，用队列实现BFS，当队列为空还未到终点，则无法达到终点(求最短步数实际上已经保证了一定能到终点)
{
node tmp=q.front();q.pop();//按队列顺序依次取出队首tmp
for(int i=0;i<8;i++)//四个方向搜索，寻找可行的下一个新节点
{
newx=tmp.x+dir[i][0];
newy=tmp.y+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&ans[newx][newy]==-1)//ans[newx][newy]=-1则说明是第一次到(newx,newy)这个点，那么到这个点的最短步数ans[newx][newy]=tmp.cnt+1
{ans[newx][newy]=tmp.cnt+1;q.push({newx,newy,tmp.cnt+1});}//新节点入队，并且走到新节点的步数是原节点的步数加一
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
j==m?printf("%-5d\n",ans[i][j]):printf("%-5d",ans[i][j]);//注意左对齐五格的输出格式
return 0;
}
SDUT 1124 飞越原野
这题有点难度，要开一个三维的vis标记数组来记录走到(newx,newy)这个节点时剩余能量为d的这种情况是否之前有过，也就是说与之前的题目相比，这题不仅要记录这个节点的位置是否走过，还要判断到这个节点位置时剩余能量为d的这种情况是否有过。 建立三维搜索思想，每次搜索在4个方向上拓展，注意分别写出步行和飞行的两种情况。
还有就是注意string类输入时不能写 | 只能写
for(int i=0;i<m;i++) | for(int i=0;i<m;i++)
for(int j=0;j<n;j++) | cin>>a[i];
cin>>a[i][j]; |
#include <bits/stdc++.h>
using namespace std;
string a[101];
int m,n,d,newx,newy,vis[101][101][101];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
struct node
{
int x,y,d,cnt;//d代表走到此节点剩余的能量，cnt表示走到此节点所用时间
};
queue<node>q;
int main()
{
ios::sync_with_stdio(false);
cin>>m>>n>>d;
for(int i=0;i<m;i++)
cin>>a[i];//注意输入string类的格式
q.push({0,0,d,0});
vis[0][0][d]=1;
int flag=0;
while(!q.empty())
{
node tmp=q.front();q.pop();
if(tmp.x==m-1&&tmp.y==n-1){printf("%d\n",tmp.cnt);flag=1;break;}//找到终点，输出答案，结束搜索
for(int i=0;i<4;i++)
{
//步行的情况，能量不变，依然为 tmp.d
newx=tmp.x+dir[i][0];
newy=tmp.y+dir[i][1];
if(newx>=0&&newx<m&&newy>=0&&newy<n&&a[newx][newy]=='P'&&vis[newx][newy][tmp.d]==0)
{vis[newx][newy][tmp.d]=1;q.push({newx,newy,tmp.d,tmp.cnt+1});}
//飞行的情况，必须飞行到陆地上，且不能超过能量消耗
for(int j=2;j<=tmp.d;j++)//j代表这一次飞行可能消耗的能量，不超过tmp.d，并且大于1，因为等于1就没必要再用飞行浪费能量了，直接步行就可以了
{
newx=tmp.x+j*dir[i][0];
newy=tmp.y+j*dir[i][1];
if(newx>=0&&newx<m&&newy>=0&&newy<n&&a[newx][newy]=='P'&&vis[newx][newy][tmp.d-j]==0)//如果新节点是陆地并且到这个节点能量为tmp.d-j的情况还没有被走过，就走这个新节点
{vis[newx][newy][tmp.d-j]=1;q.push({newx,newy,tmp.d-j,tmp.cnt+1});}
}
}
}
if(flag==0)printf("impossible\n");
return 0;
}
那么本篇文章到此就结束了，希望能帮到你，我们下周再见~
京公网安备 11010502036488号