前言

BFS,英文全称Breadth First Search,也就是广度优先搜索。
DFS用递归实现节点的拓展,而BFS用队列实现节点的拓展,用来求最短步数比较方便。
这次就不按题目的顺序写了,按题目难度写吧。前四题难度依次递增,后面还有几题是上周做过的原题我就不写了(点击此处:上周DFS训练的题解),既然用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;
}

那么本篇文章到此就结束了,希望能帮到你,我们下周再见~