🍉前言：

🌈🌈蓝桥杯还有几天就开始了，祝友友们都有好成绩鸭~

🌙🌙之前更了一篇深度优先搜索DFS的文章，今天把广度优先搜索BFS这块拼图也给补上。现在还不会BFS的小伙伴们看过来~😀相比于DFS这种要使用递归的算法，广度优先搜索就容易理解多了，相信大家练习几道题目就能轻松掌握。

题目传送门🚀🚀🚀

题目	链接
迷宫（二）	https://nanti.jisuanke.com/t/T1596
仙岛求药	https://nanti.jisuanke.com/t/T1212
红与黑	https://nanti.jisuanke.com/t/T1211
鸣人和佐助	https://nanti.jisuanke.com/t/T1214
哆啦A梦的时光机	https://nanti.jisuanke.com/t/T1257

---

🍋广度优先搜索：

👩🏻‍🏫BFS，其英文全称是Breadth First Search。

⭐广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

1. 把根节点放到队列的末尾。
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历整个树还没有找到，结束程序。

⭐看到这里一脸懵逼？没有关系，还记得之前的文章使用DFS走迷宫的问题吗，这次使用BFS试一试~

---

BFS模板例题—迷宫（二）：

蒜头君在你的帮助下终于逃出了迷宫，但是蒜头君并没有沉浸于喜悦之中，而是很快的又陷入了思考，从这个迷宫逃出的最少步数是多少呢？

输入格式

第一行输入两个整数 n 和 m，表示这是一个 n×m的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 -1−1。

数据范围

1<=n,m<=10。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

3 4
S**.
..*.
***T

样例输出1

-1

样例输入2

3 4
S**.
....
***T

样例输出2

5

👩🏻‍🏫bfs搜索过程：

（使用BFS搜索最小步数，相比与DFS，BFS更节省时间。BFS每次会优先搜索与当前位置相邻的所有点，DFS是一条路走到黑，而BFS是每次都尝试所有可能）

• 全局变量同DFS，都是一样的。

  public static int n;
  public static int m;
  public static char[][] maze;
  // 标记是否走过
  public static boolean[][] vis;
  // 能移动的方向，用数组表示更方便
  public static int[][] dir = new int[][]{
      {-1, 0}, {0, -1}, {1, 0}, {0, 1}
  };
  
  // 判断是否在迷宫内
  public static boolean inMaze(int x, int y) {
      return 0 <= x && x < n && 0 <= y && y < m;
  }
  

• Java中使用一个class表示我们走到某个位置的状态，c++可以使用结构体，我们需要记录下当前走到的位置，与走到当前位置的步数。

  // 记录走到了哪一个点
  class Node {
  
  	int x;
  	int y;
  	int step;
  
  	Node(int x, int y, int step) {
      	this.x = x;
      	this.y = y;
      	this.step = step;
  	}
  }
  

• 定义一个队列用来存放走到的位置。

  Deque<Node> que = new LinkedList<>();
  

• 先将起始点加入队列，并标记当前位置已经走过。

  que.offer(new Node(sx, sy, 0));
  vis[sx][sy] = true;
  

• 接下来只要队列不为空，就取出队首元素，判断取出的位置是否是终点，是终点就返回到达该位置的步数，如果不是终点，判断该位置的上下左右是否可以走，可以走就加入队列~

  public static int bfs(int sx, int sy) {
      Deque<Node> que = new LinkedList<>();
      // 先将初始位置加入队列，并标记为走过
      que.offer(new Node(sx, sy, 0));
      vis[sx][sy] = true;
      while (!que.isEmpty()) {
          Node currNode = que.pop();
          if (maze[currNode.x][currNode.y] == 'T')
              return currNode.step;
          // 将所有能走的位置加入队列
          for (int i = 0; i < 4; i++) {
              int tx = currNode.x + dir[i][0];
              int ty = currNode.y + dir[i][1];
              if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
                  vis[tx][ty] = true;
                  // 到达下一位置，步数加1
                  que.offer(new Node(tx, ty, currNode.step + 1));
              }
          }
      }
      return -1;
  }
  

• bfs结束以后返回的一定是最小的步数，可以想一下，每次都向四个方向搜索一步，如果返回结果为n，说明n - 1步肯定还没到终点，那么n就是最小步数。

🍦完整的代码模板（Java）：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

// 记录走到了哪一个点
class Node {

    int x;
    int y;
    int step;

    Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

public class Main {

    public static int n;
    public static int m;
    public static char[][] maze;
    // 标记是否走过
    public static boolean[][] vis;
    // 能移动的方向，用数组表示更方便
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    // 判断是否在迷宫内
    public static boolean inMaze(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    public static int bfs(int sx, int sy) {
        Deque<Node> que = new LinkedList<>();
        // 先将初始位置加入队列，并标记为走过
        que.offer(new Node(sx, sy, 0));
        vis[sx][sy] = true;
        while (!que.isEmpty()) {
            Node currNode = que.pop();
            if (maze[currNode.x][currNode.y] == 'T')
                return currNode.step;
            // 将所有能走的位置加入队列
            for (int i = 0; i < 4; i++) {
                int tx = currNode.x + dir[i][0];
                int ty = currNode.y + dir[i][1];
                if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
                    vis[tx][ty] = true;
                    que.offer(new Node(tx, ty, currNode.step + 1));
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new char[n][m];
        vis = new boolean[n][m];
        int sx = 0, sy = 0;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            // 获取起始位置
            int j = str.indexOf('S');
            if (j != -1) {
                sx = i;
                sy = j;
            }
            maze[i] = str.toCharArray();
        }
        sc.close();
        int ans = bfs(sx, sy);
        System.out.println(ans);
    }
}

---

🍑练习—仙岛求药：

👩🏻‍🏫走迷宫的模板一定要记下来，很多题目都是它的变形，甚至直接就考了个模板，比如下面这道题~

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由 M×N* 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

输入格式

第一行输入两个非零整数 M 和 N，两者均不大于 20。M 表示迷阵行数, N 表示迷阵列数。

接下来有 M行, 每行包含 N 个字符,不同字符分别代表不同含义:

\1) ‘@’：少年李逍遥所在的位置；2) ‘.’：可以安全通行的方格；3) ‘#’：有怪物的方格；4) ‘*’：仙药所在位置。

输出格式

输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 −1。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###

样例输出1

10

样例输入2

6 5
.*.#.
.#...
..##.
.....
.#...
....@

样例输出2

8

样例输入3

9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#.

样例输出3

-1

• 就是模板题，跟上一个题本质上没有任何区别，不过多解释。

🍦AC代码（Java）：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

class Node {
    
    int x;
    int y;
    int step;

    Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

public class Main {

    public static int m;
    public static int n;
    public static char[][] maze;
    public static boolean[][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    public static boolean inMaze(int x, int y) {
        return 0 <= x && x < m && 0 <= y && y < n;
    }

    public static int bfs(int sx, int sy) {
        Deque<Node> que = new LinkedList<>();
        que.offer(new Node(sx, sy, 0));
        vis[sx][sy] = true;
        while (!que.isEmpty()) {
            Node curr = que.pop();
            if (maze[curr.x][curr.y] == '*')
                return curr.step;
            for (int i = 0; i < 4; i++) {
                int tx = curr.x + dir[i][0];
                int ty = curr.y + dir[i][1];
                if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '#') {
                    vis[tx][ty] = true;
                    que.offer(new Node(tx, ty, curr.step + 1));
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        maze = new char[m][n];
        vis = new boolean[m][n];
        int sx = 0, sy = 0;
        for (int i = 0; i < m; i++) {
            String str = sc.next();
            int j = str.indexOf('@');
            if (j != -1) {
                sx = i;
                sy = j;
            }
            maze[i] = str.toCharArray();
        }
        sc.close();
        int ans = bfs(sx, sy);
        System.out.println(ans);
    }
}

---

🥝活用模板—红与黑：

👩🏻‍🏫有时候需要我们对模板稍加修改，比如这道题~

蒜厂有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。W 和 H 都不超过 20。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

输出格式

输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

6 9 
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

样例输出

45

• 本质上是让我们求和起点连通的点的数量，那么我们就不需要记录下走到每个位置所用的步数了，而是使用一个全局变量count记录下一共搜索了多少次，每搜索一个位置count就加一，最终搜索了几个位置，连通点的数量就有多少。

AC代码（Java）：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

class Node {
    
    int x;
    int y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {

    public static int w;
    public static int h;
    public static int count = 1;
    public static char[][] room;
    public static boolean[][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    public static boolean inRoom(int x, int y) {
        return 0 <= x && x < h && 0 <= y && y < w;
    }

    public static int bfs(int sx, int sy) {
        Deque<Node> que = new LinkedList<>();
        que.offer(new Node(sx, sy));
        vis[sx][sy] = true;
        while (!que.isEmpty()) {
            Node curr = que.pop();
            for (int i = 0; i < 4; i++) {
                int tx = curr.x + dir[i][0];
                int ty = curr.y + dir[i][1];
                if (inRoom(tx, ty) && !vis[tx][ty] && room[tx][ty] != '#') {
                    vis[tx][ty] = true;
                    que.offer(new Node(tx, ty));
                    count++;
                }
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w = sc.nextInt();
        h = sc.nextInt();
        room = new char[h][w];
        vis = new boolean[h][w];
        int sx = 0, sy = 0;
        for (int i = 0; i < h; i++) {
            String str = sc.next();
            int j = str.indexOf('@');
            if (j != -1) {
                sx = i;
                sy = j;
            }
            room[i] = str.toCharArray();
        }
        sc.close();
        int ans = bfs(sx, sy);
        System.out.println(ans);
    }
}

---

🍓模板变形—鸣人和佐助：

👩🏻‍🏫这道题本质上虽然还是迷宫搜索，不过题目中的条件多了一些，略有难度。

佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费 11 个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？

输入格式

输入的第一行包含三个整数：M，N，T。代表 M 行 N 列的地图和鸣人初始的查克拉数量 T。0 < M,N < 200，0≤T<10

后面是 M 行 N 列的地图，其中 @ 代表鸣人，+ 代表佐助。* 代表通路，# 代表大蛇丸的手下。

输出格式

输出包含一个整数 R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出 −1。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

4 4 1
#@##
**##
###+
****

样例输出1

6

样例输入2

4 4 2
#@##
**##
###+
****

样例输出2

4

• 这道题目难在标记数组上，需要使用三维数组标记。

• 消耗查克拉可以走#位置，只需要我们改一下判断就可以，有查克拉时上下左右都能走，所以将上下左右（只要在地图内）四个位置都加入队列，没有查克拉时就老老实实正常走。

• 使用二维标记数组，如果在没消耗查克拉的条件下搜索，*的位置标记为走过了，那么消耗查克拉走#的位置，再想搜索*的位置可能就不会搜了，然而消耗了查克拉的方案与之前不消耗查克拉的方案两者是独立的，所以我们要使用三维数组，第三维代表查克拉的数量。

• vis[x][y][t]就代表走到（x，y）位置并持有t个查克拉。

🍦AC代码（Java）：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

class Node {
    
    int x;
    int y;
    int t;
    int step;

    Node(int x, int y, int t, int step) {
        this.x = x;
        this.y = y;
        this.t = t;
        this.step = step;
    }
}

public class Main {
    
    public static int m;
    public static int n;
    public static int st;
    public static char[][] map;
    // 状态有三个，横纵坐标与查克拉数，所以使用三维标记数组
    public static boolean[][][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    public static boolean inMap(int x, int y) {
        return 0 <= x && x < m && 0 <= y && y < n;
    }

    public static int bfs(int sx, int sy, int st, int step) {
        Deque<Node> que = new LinkedList<>();
        que.offer(new Node(sx, sy, st, step));
        vis[sx][sy][st] = true;
        while (!que.isEmpty()) {
            Node curr = que.pop();
            if (map[curr.x][curr.y] == '+')
                return curr.step;
            for (int i = 0; i < 4; i++) {
                int tx = curr.x + dir[i][0];
                int ty = curr.y + dir[i][1];
                // 需要根据题目要求改变一下判断条件
                if (curr.t > 0) {
                    if (inMap(tx, ty) && !vis[tx][ty][curr.t - 1] && map[tx][ty] == '#') {
                        vis[tx][ty][curr.t - 1] = true;
                        que.offer(new Node(tx, ty, curr.t - 1, curr.step + 1));
                    }
                    if (inMap(tx, ty) && !vis[tx][ty][curr.t] && map[tx][ty] != '#') {
                        vis[tx][ty][curr.t] = true;
                        que.offer(new Node(tx, ty, curr.t, curr.step + 1));
                    }
                } else {
                    if (inMap(tx, ty) && !vis[tx][ty][curr.t] && map[tx][ty] != '#') {
                        vis[tx][ty][curr.t] = true;
                        que.offer(new Node(tx, ty, curr.t, curr.step + 1));
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        st = sc.nextInt();
        map = new char[m][n];
        vis = new boolean[m][n][15];
        int sx = 0, sy = 0;
        for (int i = 0; i < m; i++) {
            String str = sc.next();
            int j = str.indexOf('@');
            if (j != -1) {
                sx = i;
                sy = j;
            }
            map[i] = str.toCharArray();
        }
        sc.close();
        int ans = bfs(sx, sy, st, 0);
        System.out.println(ans);
    }
}

---

🍏一维搜索—哆啦A梦的时光机：

👩🏻‍🏫与前面几道迷宫问题不同，这道题让我们在一个范围上搜索，可以看作是一维的BFS。

哆啦A梦有一个神奇的道具：时光机。坐着它，大雄和他的伙伴们能穿越时空，回到过去或者去到未来。

有一天，大雄和他的伙伴们想穿越时空进行探险，可是时光机却出了一点故障，只能进行有限的时空穿越操作。大雄他们需要从现在出发，到达一个目标时间点进行探险，结束后再返回到现在，他们希望尽可能减少时光机的操作次数，你能帮助他们吗？

假设大雄和他的伙伴们出发的时间点（现在）为 S*(0<*S<1,000,000)，希望到达的时间点（目标）为 T(0<T<1,000,000)，已知时光机可以进行如下的时空穿越操作（X 为正整数）：

可以从任意时刻X穿越到 X+1 或者 X−1 时刻

可以从任意时刻X穿越到 X×2 时刻

当 X 为偶数时，可以从 X 时刻穿越到 X/2 时刻

请问，大雄和他的伙伴们从 S 时刻出发，先到达 T 时刻，再回到 S 时刻最少需要多少次时空穿越操作？

输入格式

输入的第一个数是一个正整数 N*，表示测试数据一共有 N* 组（0<N<20）。之后有 N 行，每一行包含两个正整数 S 和 T，表示出发和到达时间点。

输出格式

输出包括N行，每一行一个正整数，表示每组测试数据对应的最少时光机操作次数。

样例解释

对于 S*=5，T*=17：
操作如下：5->4->8->16->17->16->8->4->5

对于 S*=4，T*=8：操作如下：4->8->4

输出时每行末尾的多余空格，不影响答案正确性

样例输入

2
5 17
4 8

样例输出

8
2

• 将时间看成是数轴的话，本质上是一维的搜索，其实都是一样的模板，还是需要用一个额外的class记录状态，记录到达的时间与穿越次数。

• 搜索的位置根据题目修改即可，迷宫是上下左右尝试搜索，这里根据题目要求来。

🍦AC代码（Java）：

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

class Node {

    int time;
    int count;

    Node(int time, int count) {
        this.time = time;
        this.count = count;
    }
}

public class Main {

    public static int s;
    public static int t;
    public static boolean vis[] = new boolean[1000000];

    public static boolean isValid(int time) {
        return 0 < time && time < 1000000;
    }

    public static int bfs(int s, int t) {
        Arrays.fill(vis, false);
        Deque<Node> que = new LinkedList<>();
        que.offer(new Node(s, 0));
        vis[s] = true;
        while (!que.isEmpty()) {
            Node curr = que.pop();
            if (curr.time == t) {
                return curr.count;
            }
            int next = curr.time + 1;
            if (isValid(next) && !vis[next]) {
                vis[next] = true;
                que.offer(new Node(next, curr.count + 1));
            }
            next = curr.time - 1;
            if (isValid(next) && !vis[next]) {
                vis[next] = true;
                que.offer(new Node(next, curr.count + 1));
            }
            next = curr.time << 1;
            if (isValid(next) && !vis[next]) {
                vis[next] = true;
                que.offer(new Node(next, curr.count + 1));
            }
            if (curr.time % 2 == 0) {
                next = curr.time >> 1;
                if (isValid(next) && !vis[next]) {
                    vis[next] = true;
                    que.offer(new Node(next, curr.count + 1));
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            s = sc.nextInt();
            t = sc.nextInt();
            int ans = bfs(s, t) + bfs(t, s);
            System.out.println(ans);
        }
        sc.close();
    }
}

---

🍌🍌🍌
BFS广度优先搜索，并不是很难理解的内容，动动小手练习一下就能掌握了，BFS的模板一定要记牢哦~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲一枚，请大佬们多多关照~