使用 BFS 解决 最短路问题

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏： 优选算法专题

目录

1926.迷宫中离入口最近的出口

433.最小基因变化

127.单词接龙

675.为高尔夫比赛砍树

---

 

1926.迷宫中离入口最近的出口

题目：

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

示例 1：

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。

示例 2：

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。

示例 3：

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

提示：

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 要么是 '.' ，要么是 '+' 。
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance 一定是空格子。

思路：本题属于迷宫中寻找最短路径，一般采取的是DFS或BFS，这里统一采取BFS的方式。由于BFS是一层一层的往外走，因此我们在将本层的结点入队之后，再去将下一层结点入队时，得一次性将本层节点全部出队，将下一层的结点入队。这样才能确保全部都走了一步。这里可以统计本层的结点个数，然后循环的将本层节点出队，将下一层结点入队，如果在入队时，发现已经到了出口时，就可以直接返回走的步数（也就是BFS的层数）。

代码实现：

class Solution {public int nearestExit(char[][] maze, int[] entrance) {int[] dx = {1,-1,0,0};int[] dy = {0,0,1,-1};int m = maze.length, n = maze[0].length;boolean[][] visited = new boolean[m][n];Queue<int[]> queue = new LinkedList<>();queue.offer(entrance);visited[entrance[0]][entrance[1]] = true; // 标记已经访问过了int ret = 0; // 记录层数// 从当前位置开始BFSwhile (!queue.isEmpty()) {ret++;int size = queue.size();// 确保每一层都走完了while (size-- != 0) {int[] arr = queue.poll();for (int k = 0; k < 4; k++) {int sr = arr[0] + dx[k], sc = arr[1] + dy[k];if (sr >= 0 && sr < m && sc >= 0 && sc < n && maze[sr][sc] == '.' && !visited[sr][sc]) {// 判断是否走到出口了if (sr == 0 || sr == m-1 || sc == 0 || sc == n-1) {return ret;}queue.offer(new int[]{sr, sc});visited[sr][sc] = true;}}}}return -1;}
}

433.最小基因变化

题目：

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

• start.length == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

思路：本题可以采用决策树的思想来解决。把题目给的原始字符串看成起点，而每一次变化的结果看成树的一个结点，那么从原始字符串到目标字符串的变化过程都在决策树中，而我们只需要遍历这个树即可。同样这里采用BFS的方式，由于题目求的是最小变化次数，即原始字符串到目标字符串的最短距离。因此，我们在遍历时，要将本层的结点同时出队，将下一层的结点同时入队。

注意：每次变化后的结果必须是在 bank数组 中。

代码实现：

class Solution {public int minMutation(String startGene, String endGene, String[] bank) {Map<String, Boolean> hash = new HashMap<>(); // 记录基因库中的序列Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列for (String s : bank) {hash.put(s,true);}char[] changes = {'A','C','G','T'};// 判断 特殊情况if (startGene.equals(endGene)) {return 0;}if (!hash.containsKey(endGene)) { // 不存在库中return -1;}// 使用BFS遍历决策树Queue<String> queue = new LinkedList<>();queue.offer(startGene);visited.put(startGene, true);int ret = 0; // 记录走的步数while (!queue.isEmpty()) {ret++;int size = queue.size(); // 记录当前层的个数while (size-- != 0) {String s = queue.poll();// 字符串的每一位都发生了变化for (int i = 0; i < 8; i++) { // 字符串的长度为8char[] tmp = s.toCharArray();for (int j = 0; j < 4; j++) {tmp[i] = changes[j]; // 将第i位的字符改为另外的字符String next = new String(tmp);// 判断next是否符合要求（存在bank库中 并且 未被访问）if (hash.containsKey(next) && !visited.containsKey(next)) {if (next.equals(endGene)) {return ret;}queue.offer(next);visited.put(next, true);}}}}}return -1;}
}

127.单词接龙

题目：

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

思路： 本题和上一题几乎是一模一样的思路。同样也是采用BFS对决策树进行遍历求出最短路径即可。

代码实现：

错误代码（超时）：

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列// 判断特殊情况if (beginWord.equals(endWord)) {return 0;}if (!wordList.contains(endWord)) {return 0;}Queue<String> queue = new LinkedList<>();queue.offer(beginWord);visited.put(beginWord, true);int ret = 1; // 这里求的是单词数目，第一层也有一个单词while (!queue.isEmpty()) {ret++;int size = queue.size(); // 求出当前层的个数while (size-- != 0) {String s = queue.poll();int n = s.length(); // 这里并未说明字符串的长度固定为多少for (int i = 0; i < n; i++) {char[] tmp = s.toCharArray();for (char j = 'a'; j <= 'z'; j++) { // 24个字母都试一下if (tmp[i] == j) { // 相同就不需要走下去了continue;}tmp[i] = j; // 将第i位的字符改为另外的字符String next = new String(tmp);// 判断是否符合要求（变化后的结果在字典中、未被访问过）if (wordList.contains(next) && !visited.containsKey(next)) {if (endWord.equals(next)) {return ret;}queue.offer(next);visited.put(next, true);}}}}}return 0;}
}

注意：上面的代码由于在查询每次变化后的结果是否是有效时，都是在List中去查找，时间复杂度是O(N)，因此最终就会超时。这里就可以先将List中的元素加入哈希表中，这样后续查询的时间复杂度就是O(1)了。 

正确代码：

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列Map<String, Boolean> hash = new HashMap<>();for (String s : wordList) {hash.put(s, true);}// 判断特殊情况if (beginWord.equals(endWord)) {return 0;}if (!hash.containsKey(endWord)) {return 0;}Queue<String> queue = new LinkedList<>();queue.offer(beginWord);visited.put(beginWord, true);int ret = 1; // 这里求的是单词数目，第一层也有一个单词while (!queue.isEmpty()) {ret++;int size = queue.size(); // 求出当前层的个数while (size-- != 0) {String s = queue.poll();int n = s.length(); // 这里并未说明字符串的长度固定为多少for (int i = 0; i < n; i++) {char[] tmp = s.toCharArray();for (char j = 'a'; j <= 'z'; j++) { // 24个字母都试一下if (tmp[i] == j) { // 相同就不需要走下去了continue;}tmp[i] = j; // 将第i位的字符改为另外的字符String next = new String(tmp);// 判断是否符合要求（变化后的结果在字典中、未被访问过）if (hash.containsKey(next) && !visited.containsKey(next)) {if (endWord.equals(next)) {return ret;}queue.offer(next);visited.put(next, true);}}}}}return 0;}
}

675.为高尔夫比赛砍树

题目：

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

• 0 表示障碍，无法触碰
• 1 表示地面，可以行走
• 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

提示：

• m == forest.length
• n == forest[i].length
• 1 <= m, n <= 50
• 0 <= forest[i][j] <= 109

思路：题目是让我们求出砍完所有树，所需的最小步数：

由于最开始我们是不知道高度最小的树在哪里，以及后面怎么走都是不确定的（不能站在上帝视角），因此我们得预先处理一下数组，得到从小到大的砍树顺序。接下来就是求从某一点到另外一点的最短路径（这就是最开始的迷宫问题：从入口到出口的最短距离），最后将全部的计算结果相加即可。 

代码实现：

class Solution {int m;int n;public int cutOffTree(List<List<Integer>> forest) {m = forest.size();n = forest.get(0).size();// 1、确定砍树的顺序（存储下标）// 将所有树都加入数组List<int[]> trees = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (forest.get(i).get(j) > 1) { // 存储树的下标trees.add(new int[]{i, j});}}}// 对数组内的树大小进行排序// 注意：这里的a，b都是下标数组，而不是树的高度Collections.sort(trees, (a, b) -> {return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);});// 2、从起点出发，寻找 到下一棵树的最短距离int ret = 0;int bx = 0, by = 0;for (int[] arr : trees) {int step = bfs(forest, bx, by, arr[0], arr[1]); // 求出最小值if (step == -1) {return -1; // 到达不了，就直接返回即可}// 更新起始位置bx = arr[0];by = arr[1];ret += step;}return ret;}int[] dx = {1,-1,0,0};int[] dy = {0,0,-1,1};boolean[][] visited;private int bfs(List<List<Integer>> forest, int bx, int by, int ex, int ey) {// 如果起始位置和结束位置是同一个位置，则直接返回if (bx == ex && by == ey) {return 0;}visited = new boolean[m][n];Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{bx, by});visited[bx][by] = true;int ret = 0;while (!queue.isEmpty()) {ret++;int size = queue.size();// 确保同一层的元素全部出完while (size-- != 0) {int[] arr = queue.poll();for (int k = 0; k < 4; k++) {int sr = arr[0] + dx[k], sc = arr[1] + dy[k];// 判断 参数是否正常、是否可以通过、是否为未访问if (sr >= 0 && sr < m && sc >= 0 && sc < n&& forest.get(sr).get(sc) >= 1 && !visited[sr][sc]) {if (sr == ex && sc == ey) {return ret;}queue.offer(new int[]{sr, sc});visited[sr][sc] = true;}}}}return -1;}
}

好啦！本期 使用 BFS 解决 最短路问题 的刷题之旅 就到此结束啦！我们下一期再一起学习吧！