在上一次解救小玄的行动中，我们使用了深度优先搜索的方法。今天，我们将介绍另外一种方法来解决这个问题——广度优先搜索（Breadth First Search,BFS）,也称为宽度优先搜索。
问题解析
最开始时，小澈在迷宫（1,1）处，他可以选择往右或者是往下走。选择我们采用“一层一层”拓展的方法来找到小玄。拓展时每发现一个点就将这个点加到队列中，直到走到小澈的位置（P,Q）时为止。
最开始时，小澈在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）。
但是小玄并不在这两个点上，那小澈只能通过（1,2）和（2,1）这两个点继续往下走。比如说从（1,2）后，可以到达（2,2）和（3,1）。此时你会发现（2,2）这个点既可以被从（1,2）到达，也可以从（2,1）到达，并且都只使用了两步。为了防止一个点被多次走到，我们需要一个数组来记录一个点是否被走到过。
此时小澈2步可以走到的点就全部走到了，有（2,2）和（3,1），可是小玄并不在这两个点上。没有别的方法，还只能继续向下尝试，看看通过（2,2）和（3,1）还有没有哪些能够新到达的点。通过（2,2）这个点我们能到达（2,3）和（3,2），通过（3,1）我们可以到达（3,2）和（4,1）。现在3步能够到达的点有（2,3）（3,2）（4,1），依旧没有小玄所在的点，我们需要重复刚才的方法，直到找到小玄所在的点为止。
代码实现
回顾刚才的算法，可以用一个队列来模拟这个过程。这里我们还是用一个结构体来实现队列。
struct note { int x; //横坐标 int y; //纵坐标 int s; //步数 }; struct note que[2501]; //因为地图大小不超过 50*50，因此队列扩展不会超过2500个 int head, tail; int a[51][51] = { 0 }; //用来储存地图 int book[51][51] = { 0 }; //数组book的作用是记录哪些点已经在队列中了，防止一个点被重复扩展，并全部初始化为0 //最开始的时候需要进行队列初始化，即将队列设置为空 head = 1; tail = 1; //第一步将(1,1)加入队列，并将队列设置为空 que[tail].x = 1; que[tail].y = 1; que[tail].s = 0; tail++; book[1][1] = 1;
然后从（1,1）开始，向右尝试走到了（1,2）
tx = que[head].x; ty = que[head].y + 1;需要判断（1,2）是否越界
if (tx < 1 || tx > n || wy < 1 || ty >m) continue;在判断（1,2）是否为障碍物或者是已经在路径中
if (a[tx][ty] == 0 && book[tx][ty] == 0) { }如果满足以上条件，则将（1,2）入队，并标记该点已经走过。
//把这个点标记为走过 book[tx][ty] = 1; //注意宽搜每个点通常只入队一次，和深度不同，不需要将book数组还原 //插入新的点到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; //步数是小澈的步数+1 tail++;
接下来还要继续往其他方向走。这里还是规定一个顺序，即按照顺时针的方向来尝试（也就是以右，下，左，上的顺序尝试）。我们发现（1,1）还是可以到达（2,1）因此也需要将（2,1）入列，代码与刚才对（1,2）的操作是一样的。
对我们来说，其实（1,1）也就是没有用的了，此时我们将（1,1）出队。操作很简单，就一句话。
head++；接下来我们需要在刚才新扩展出来的（1,2）和（2,1）两个点的基础上继续向下探索。到目前为止我们已经扩展出了从起点出发一步内可以到达的所有点。因为我们还没到达小玄的位置，所以我们需要继续向下探索。
（1,1）出队后，现在队列的head正好指向了（1,2）这个点，现在我们需要通过这个点继续拓展，通过（1,2）可以到达（2,2），并将（2,2）也加入队列。
（1,2）这个点处理完，对我们来说也没什么用了，于是将（1,2）出队。（1,2）出队后，head指向了（2,1）这个点。通过（2,1）我们可以到达（2,2）和（3,1），但因为（2,2）已经在队列中了，所以我们只需要将（3,1）入队。
到目前为止我们已经扩展了从起点出发两点内可以到达的所有点，可是依旧没有到达小玄的位置，因此还需要继续，直到走到小玄所在的点，算法结束
为了方便四个方向拓展，与上一篇一样我们需要一个next数组
int next[4][2] = { {0,1}, //向右走 {1.0}, //向下走 {0, - 1},//向左走 {-1,0}, //向上走 };
完整代码
#include <stdio.h> struct note { int x; //横坐标 int y; //纵坐标 int s; //步数 }; int main() { struct note que[2501]; //因为地图大小不超过 50*50，因此队列扩展不会超过2500个 int a[51][51] = { 0 }; //用来储存地图 int book[51][51] = { 0 }; //数组book的作用是记录哪些点已经在队列中了，防止一个点被重复扩展，并全部初始化为0 //定义一个用来表示走的方向的数组 int next[4][2] = { {0,1}, //向右走 {1.0}, //向下走 {0, -1},//向左走 {-1,0}, //向上走 }; int head, tail; int i, j, k, nm, startx, starty, p, q, tx, ty, flag; scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } //最开始的时候需要进行队列初始化，即将队列设置为空 head = 1; tail = 1; //第一步将(1,1)加入队列，并将队列设置为空 que[tail].x = startx; que[tail].y = starty; que[tail].s = 0; tail++; book[startx][starty] = 1; flag = 0; //用来标记是否到达目标点，0表示暂时还没有到达，1表示达到 //当队列不为空时循环 while (head < tail) { //枚举四个方向 for (k = 0; k <= 3; k++) { //计算下一个点的坐标 tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; //判断是否越界 if (tx < 1 || tx > n || wy < 1 || ty >m) continue; if (a[tx][ty] == 0 && book[tx][ty] == 0) { //把这个点标记为走过 //注意宽搜每个点只入队一次，所以和深搜不同，不需要将book还原 book[tx][ty] = 1; //插入新的点到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; } //如果目标点到了，停止拓展，任务结束，退出循环 if (tx == p && ty == q) { //注意下面两句的位置不要写颠倒了 flag = 1; break; } if (flag == 1) break; head++; //注意这个地方千万不要忘记，当一个点拓展结束后，需要head++才能对后面的点进行再拓展 } } //打印队列中末尾最后一个点（目标点）的步数 //注意tail是指向队列队尾的下一个位置，所以这需要-1 printf("%d", que[tail - 1].s); return 0; }
额外知识
1959年，Edward F.Moore率先在“如何在迷宫中找到出路”这一问题中提出了广度优先搜索算法。1961年，C.Y.Lee在“电路板布线”这一个问题中也提出了相同的算法。
今天的文章就到此结束啦，如果觉得有帮助，请给小玄：
