[数据结构与算法] 【蓝桥杯Java组】刷了这五道题不信你还不会BFS（广度优先搜索）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【蓝桥杯Java组】刷了这五道题不信你还不会BFS（广度优先搜索） -> 正文阅读

[数据结构与算法]【蓝桥杯Java组】刷了这五道题不信你还不会BFS（广度优先搜索）

header

🍉前言：

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

🌙🌙之前更了一篇深度优先搜索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）来实现，整个过程也可以看做一个倒立的树形：

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

?看到这里一脸懵逼？没有关系，还记得之前的文章使用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();
    }
}