BFS 算法专题（三）：BFS 解决边权为 1 的最短路问题
目录
1. 迷宫中离入口最近的出口
1.1 算法原理
1.2 算法代码
2. 最小基因变化 ★★★
2.1 算法原理
2.2 算法代码
3. 单词接龙
3.1 算法原理
3.2 算法代码
4. 为高尔夫比赛砍树 (hard)
4.1 算法原理
4.2 算法代码
1. 迷宫中离入口最近的出口
. - 力扣（LeetCode）
1.1 算法原理
核心问题: 图论 => 边权为1/边权相同 的最短路径问题
解法: 从起点开始, 进行 BFS 扩展, 第一次到达终点时, 扩展的层数, 就是最短的路径.
如何记录 BFS 扩展的层数呢??
--- 借助每一层中节点的数量(queue.size()), 使用变量 ret 记录扩展的层数.
1.2 算法代码
class Solution {public int nearestExit(char[][] maze, int[] entrance) {int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };// 记录到达终点时, BFS 的层数int ret = 0;int m = maze.length, n = maze[0].length;boolean[][] check = new boolean[m][n];Queue<int[]> q = new LinkedList<>();q.offer(entrance);check[entrance[0]][entrance[1]] = true;while (!q.isEmpty()) {int size = q.size();ret++;while (size-- != 0) {int[] tmp = q.poll();int a = tmp[0], b = tmp[1];for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && maze[x][y] == '.') {if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return ret;q.offer(new int[] { x, y });check[x][y] = true;}}}}return -1;}
}2. 最小基因变化 ★★★
. - 力扣（LeetCode）
2.1 算法原理
问题转化: 转化为 => 图论 边权为1的最短路问题
- 每变一个字符(基因的变化)看做一步, BFS 选出达到目标基因序列时的最短路.
- 注意: 不能重复搜索已经搜索过的状态
- 注意: 经过变化的字符串, 应该在 bank 基因库中存在
- 使用 哈希表 标记已经搜索过的状态
- 使用 哈希表 保存基因库中的字符(便于查找变化的字符串是否在基因库中)
2.2 算法代码
class Solution {public int minMutation(String startGene, String endGene, String[] bank) {Queue<String> q = new LinkedList<>();// 判断是否重复转化Set<String> check = new HashSet<>();// 判断基因库中是否存在Set<String> hash = new HashSet<>();for(String s : bank) hash.add(s);if(!hash.contains(endGene)) return -1;if(startGene.equals(endGene)) return 0;char[] change = {'A', 'C', 'G', 'T'};int ret = 0;q.offer(startGene);check.add(startGene);while(!q.isEmpty()) {int size = q.size();ret++;while(size-- != 0) {String s = q.poll();for(int i = 0; i < 8; i++) {char[] tmp = s.toCharArray();for(int j = 0; j < 4; j++) {tmp[i] = change[j];String next = new String(tmp);if(hash.contains(next) && !check.contains(next)) {if(next.equals(endGene)) return ret;check.add(next);q.offer(next);}}}}}return -1;}
}3. 单词接龙
. - 力扣（LeetCode）
3.1 算法原理
-
本题解法与上题解法完全一致.
-
只不过返回值略有差异. 本题返回达到目标字符串时, 所涉及到的最少的字符串的个数(最短路 +1)
3.2 算法代码
class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 把字典中的字符串, 放到哈希表中 => 查找效率 O(1)Set<String> hash = new HashSet<>(wordList);if(!hash.contains(endWord)) return 0;int n = beginWord.length();// 判断是否重复转化Set<String> check = new HashSet<>();Queue<String> q = new LinkedList<>();int step = 0;q.offer(beginWord);check.add(beginWord);while(!q.isEmpty()) {int size = q.size();step++;while(size-- != 0) {String s = q.poll();for(int i = 0; i < n; i++) {char[] tmp = s.toCharArray();for(char ch = 'a'; ch <= 'z'; ch++) {tmp[i] = ch;String next = new String(tmp);if(hash.contains(next) && !check.contains(next)) {if(next.equals(endWord)) return step + 1;q.offer(next);check.add(next);}}}}}return 0;}
}4. 为高尔夫比赛砍树 (hard)
. - 力扣（LeetCode）
4.1 算法原理
-
对砍树的顺序做好记录(所砍树的高度应从小到大), 并记录好每一颗树的位置.
-
从起点开始, 对这些位置依次进行 BFS, 找出到达这些位置的最短路.
-
返回到达所有位置所需最少步数之和
4.2 算法代码
class Solution {int m, n;int[] dx = new int[] { 1, -1, 0, 0 };int[] dy = new int[] { 0, 0, 1, -1 };public int cutOffTree(List<List<Integer>> forest) {m = forest.size(); n = forest.get(0).size();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});}}// 依次需要砍的树(树的高度从小到大)Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));int step = 0;int curX = 0, curY = 0;for (int[] t : trees) {int x = t[0], y = t[1];int ret = bfs(x, y, curX, curY, forest);if (ret == -1) return -1;step += ret;curX = x;curY = y;}return step;}public int bfs(int x, int y, int curX, int curY, List<List<Integer>> forest) {int ret = 0;if (curX == x && curY == y) return 0;boolean[][] check = new boolean[m][n];Queue<int[]> q = new LinkedList<>();q.offer(new int[] { curX, curY });check[curX][curY] = true;while (!q.isEmpty()) {int size = q.size();ret++;while (size-- != 0) {int[] t = q.poll();int a = t[0], b = t[1];for (int k = 0; k < 4; k++) {int i = a + dx[k], j = b + dy[k];if (i >= 0 && i < m && j >= 0 && j < n && forest.get(i).get(j) != 0 && !check[i][j]) {if (forest.get(i).get(j) == forest.get(x).get(y))return ret;q.offer(new int[] { i, j });check[i][j] = true;}}}}return -1;}
}
END