【蓝桥杯Java组】刷了这五道题不信你还不会BFS（广度优先搜索）

🍉前言：

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

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

题目传送门🚀🚀🚀

🍋广度优先搜索：

👩🏻‍🏫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 4S**...*.***T

样例输出1

-1

样例输入2

3 4S**.....***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

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

样例输入

25 174 8

样例输出

82

• 将时间看成是数轴的话，本质上是一维的搜索，其实都是一样的模板，还是需要用一个额外的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_晗，计科专业大学牲一枚，请大佬们多多关照~