BFS

一、BFS

       BFS，即为宽度优先搜索，思路是先搜索距离初始状态近的状态。按照初始状态->只需一次就可以到达的状态->只需两次就可以。。。。。。

      宽度优先搜索采用了队列的思想

二、例题

例一、迷宫最短路径

题目    给定一个大小为N*M的迷宫，迷宫由通道和墙壁组成，，每一步可以向左右上下四个方向走一步，请计算从出发点到终点最少需要多少步，若不能到达终点则输出‘NO’

n,m<=100

input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
SW.W.....WW.
W.W.W.....W.
.W.WG.....W.
..W.......W

output

12

题解：因为如果第一步能到达，那么肯定会舍弃第二步，所以可以用bfs算法来解决

代码：

#include<iostream>
#include<algorithm>
#include<utility>
#include<string>
#include<queue>
#define maxn 105
#define INF 1000000
using namespace std;
typedef pair<int ,int> P;
int bx,by;//初始点的坐标
int ex,ey;//终点的坐标
int N,M;//行数和列数
int a[maxn][maxn];//记录是否被标记
string s[maxn];//记录地图
queue<P> que;//bfs的队列
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};//上下左右移动
int bfs()
{
    while(!que.empty())
    {
        P p=que.front();
        que.pop();
        int x=p.first,y=p.second;
        if(x==ex&&y==ey) break;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=0&&xx<N&&yy>=0&&yy<M&&a[xx][yy]==INF&&s[xx][yy]!=‘W‘)
            {
                que.push(P(xx,yy));
                a[xx][yy]=a[x][y]+1;
            }
        }
    }
    return a[ex][ey];
}
int main()
{
    while(cin>>N>>M&&M)
    {
        while(!que.empty())
            que.pop();//清空队列
        for(int i=0;i<N;i++)
            cin>>s[i];
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                a[i][j]=INF;
                if(s[i][j]==‘S‘)
                {
                    bx=i;
                    by=j;
                }
                if(s[i][j]==‘G‘)
                {
                    ex=i;
                    ey=j;
                }
            }
        }
        a[bx][by]=0;
        que.push(P(bx,by));
        int ans=bfs();
        cout<<ans<<endl;
    }
    return 0;
}
例二、数字迷宫

描述这有一个迷宫，有N行和M列：

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入行数和列数，随后输入N行M列数字

输入一个整数n（0<n<=100），表示有n组测试数据;

随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入 

            9 9
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 0 1 0 1 1 0 1 1
1 0 0 0 0 1 0 0 1
1 1 0 1 0 1 0 0 1
1 1 0 1 0 1 0 0 1
1 1 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1   

2
 3 1  5 7

  3 1  6 7
样例输出
    12
    11

代码：

#include<iostream>
#include<algorithm>
#include<utility>
#include<string>
#include<queue>
#define maxn 105
#define INF 1000000
using namespace std;
typedef pair<int,int> P;
int bx,by;//初始点的坐标
int co,ex,ey;//终点的坐标
int N,M;//行数和列数
int a[maxn][maxn];//记录是否被标记
int s[maxn][maxn];//记录地图
queue<P> que;//bfs的队列
int dx[]= {0,0,1,-1},dy[]= {1,-1,0,0}; //上下左右移动
int bfs()
{
    while(!que.empty())
    {
        P p=que.front();
        que.pop();
        int x=p.first,y=p.second;
        if(x==ex&&y==ey)
            break;
        for(int i=0; i<4; i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=0&&xx<N&&yy>=0&&yy<M&&a[xx][yy]==INF&&s[xx][yy]!=1)
            {
                que.push(P(xx,yy));
                a[xx][yy]=a[x][y]+1;
            }
        }
    }
    return a[ex][ey];
}
int main()
{
    while(cin>>N>>M&&M)
    {
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                cin>>s[i][j];
        cin>>co;
        while(co--)
        {
            cin>>bx>>by>>ex>>ey;
            while(!que.empty())
                que.pop();//清空队列
            for(int i=0; i<N; i++)
                for(int j=0; j<M; j++)
                    a[i][j]=INF;
            a[bx][by]=0;
            que.push(P(bx,by));
            int ans=bfs();
            cout<<ans<<endl;
        }

    }
    return 0;
}

BFS

原文：https://www.cnblogs.com/Joe2019/p/13363298.html