有这样一个**矩阵**，指定 A、B 两点和一些障碍物，要求从 A 走向 B。假设**只能向上、下、左、右四个方向移动**，求从 A 到 B 的**最短距离（此处指曼哈顿距离）**。

![bfs](https://raw.githubusercontent.com/Ratizux/Ratizux.github.io/master/res/misc/bfs-from-distance/bfs.png)

一种很容易想到的解法就是以 A 为中心依次标记到 A 的最短距离。

![bfs-begin](https://raw.githubusercontent.com/Ratizux/Ratizux.github.io/master/res/misc/bfs-from-distance/bfs-begin.png)

那么很明显，从 A 到 B 最短要走 8 格。

广搜的一种应用，就是最短路问题。

# 队列

广度优先搜索一般用队列来维护。队列，具有"先进先出"的特性的数据结构，即**先被压入队列的元素，必定先被弹出**。正是这种特性让广搜得以用队列轻松实现。

```
定义：queue <int> a;
插入队尾：a.push(x);
删除队首：a.pop();
查询队尾：a.back();
查询队首：a.front();
查询长度：a.size();
查询是否为空：a.empty();
```

于是我们可以先定义三个队列：`px`、`py`、`x`，用来记录要将第几行，第几列的数据设为几。

由于先进先出的特性，向队列中压入元素并不会打乱原有元素的顺序。这样才能保证设置数据（也就是最短距离）的顺序是从小到大的。

此外，还要设置一个整数二维数组来存放每个方格离 A 的最短距离，和一个布尔型数组来标记某个方格是否是可修改的以此避免重复的搜索并避开障碍。

# 思路

设置一个条件为队列非空的循环，每次从队列中读取并弹出（可以理解为删去）"坐标"和"距离"数据。

之后，设置好指定"坐标"的"距离"数据。然后分别检查四周的方格是否被标记为可修改的（避免重复计算）：如果是，就设定四周"坐标"的"距离"为当前所在方格的"距离"+1。

计算结束之后，队列为空，循环结束。这时直接输出 B 坐标所被标记的"距离"即可。

# 代码

```
#include <iostream>
#include <queue> //这里要用到队列，所以要加上队列的头文件。
using namespace std;
int main()
{
    queue <int> px,py,x; //定义队列。
    
    px.push(0);py.push(0);x.push(0); //将 A 点加入队列。"距离"为0，因为A到自身的距离肯定是0。
    
    int posx,posy,dt; //定义循环中使用的"坐标"和"距离"数据，免得再一次次读取。
    int b[5][5];bool lock[5][5]={false}; //设置整数和布尔二维数组。此例矩阵的规格是5*5，所以数组大小也不能小于它。
    
    lock[1][0]=true;lock[1][1]=true;lock[1][2]=true;lock[1][3]=true; //记录障碍物。
    
    while(!x.empty()) //循环条件是队列非空。因为这三个队列的操作是同步的，所以只需要判断一个就可以。
    {
        posx=px.front();px.pop(); //从队列中读入数据。
        posy=py.front();py.pop();
        dt=x.front();x.pop();
        
        b[posx][posy]=dt; //设定指定"坐标"的"距离"数据。
        
        dt++; //"距离"+1。
        
        if(!lock[posx-1][posy] && posx-1>=0 && posx-1<=4 && posy>=0 && posy<=4) //判断方格是否可修改且不越界。
        {px.push(posx-1);py.push(posy);x.push(dt);lock[posx-1][posy]=true;} //加入队列，别忘记标记方格为不可修改。
        if(!lock[posx+1][posy] && posx+1>=0 && posx+1<=4 && posy>=0 && posy<=4)
        {px.push(posx+1);py.push(posy);x.push(dt);lock[posx+1][posy]=true;}
        if(!lock[posx][posy-1] && posx>=0 && posx<=4 && posy-1>=0 && posy-1<=4)
        {px.push(posx);py.push(posy-1);x.push(dt);lock[posx][posy-1]=true;}
        if(!lock[posx][posy+1] && posx>=0 && posx<=4 && posy+1>=0 && posy+1<=4)
        {px.push(posx);py.push(posy+1);x.push(dt);lock[posx][posy+1]=true;}
    }
    cout<<b[2][2]; //直接输出B的坐标即可。
    }
```

这是广搜的最简单实现。当然，有相当大的优化空间。比如检测到 B 所在的方格已经被搜索过后直接结束循环，或者同时从 A、B 两点开始搜索。