广度优先搜索其实简单的理解就是从起点开始一层一层的扩散出去，要实现这个一层一层的扩散就要用到队列的先进先出的思想，所以一般我们都用队列来实现广度优先搜索算法。

迷宫
题目描述：
小 A 同学现在被困在了一个迷宫里面，他很想从迷宫中走出来，他可以 向上、向下、向左、向右移动、每移动一格都需要花费 1 秒的时间，不能够走到 边界之外。假设小 A 现在的位置在 S，迷宫的出口在 E，迷宫可能有多个出口。 问小 A 想要走到迷宫出口最少需要花费多少秒？
输入描述：
有多组测试数据。
第一行输入两个正整数 H（0 < H <= 100）和 W（0 < W <= 100），分别表示迷
宫的高和宽。
接下来 H 行，每行 W 个字符（其中‘*’表示路，‘#’表示墙，‘S’表示小 A
的位置，‘E’表示迷宫出口）。
当 H 与 W 都等于 0 时程序结束。
输出描述：
输出小 A 走到迷宫出口最少需要花费多少秒，如果永远无法走到出口则输出“-1”。
输入样例#:
3 3
S*#
**#
#*E
0 0
输出样例#:
4
题目来源：
DreamJudge 1563

题目解析：直接使用广度优先搜索模板即可。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 100 + 5;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
struct node {
    int x, y;
    int step;
};
//使用广度优先搜索求解  
int bfs(int sx, int sy) {
    memset(vis, 0, sizeof(vis));
    queue<node> q;//使用队列来维护一层层发散的优先级  
    q.push(node{sx, sy, 0});
    vis[sx][sy] = 1;
    int ans = -1;
    while(!q.empty()) {
        node now = q.front();
        q.pop();
        if (mpt[now.x][now.y] == 'E') {//找到终点  
            ans = now.step;
            break;
        }
        for (int i = 0; i < 4; i++) {//上下左右四个方向  
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if ((mpt[nx][ny] == '*' || mpt[nx][ny] == 'E')&&vis[nx][ny] == 0) {
                q.push(node{n...

练习题目

DreamJudge 1308 迷宫逃离2
DreamJudge 1124 生化武器2
DreamJudge 1126 生化武器