图的广度优先搜索 (Graph BFS)
图 BFS 是求最短路径的最优策略。在无权图中，从起点第一次到达目标节点的层数即为最短距离。
909. 蛇梯棋 (Snakes and Ladders)
题目描述
给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n^2 编号，编号遵循 蛇梯棋规则 ，从左下角 (n - 1, 0) 开始（编号为 1），每一行交替方向。
玩家从方格 1 开始。在每一回合，玩家从当前方格 curr 开始，投掷一个 六面 骰子，落在 [curr + 1, min(curr + 6, n^2)] 范围内的任意方格 next 。
- 如果
next有一个传送门（即board[r][c] != -1），玩家必须传送到board[r][c]。 - 如果
next没有传送门，玩家停在next。
返回达到编号为 n^2 的方格所需的最少移动次数。如果无法到达，返回 -1 。
解题思路
BFS 层次模拟 + 坐标映射。
- BFS 每一层代表一步操作。
- 定义
getPos(int move, int n)辅助函数，将数字位置映射回(r, c)二维坐标，注意行列蛇形交替方向的变化。 - 状态记录
visited防止重复。
Java 代码实现
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] visited = new boolean[n * n + 1];
Queue<Integer> q = new LinkedList<>();
q.offer(1);
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int curr = q.poll();
if (curr == n * n) return steps;
for (int next = curr + 1; next <= Math.min(curr + 6, n * n); next++) {
int[] rc = getRC(next, n);
int dest = board[rc[0]][rc[1]] == -1 ? next : board[rc[0]][rc[1]];
if (!visited[dest]) {
visited[dest] = true;
q.offer(dest);
}
}
}
steps++;
}
return -1;
}
private int[] getRC(int move, int n) {
int r = (move - 1) / n, c = (move - 1) % n;
if (r % 2 == 1) c = (n - 1) - c;
return new int[]{n - 1 - r, c};
}
}
433. 最小基因变化 (Minimum Genetic Mutation)
题目描述
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"是一次基因变化。
此外，还有一个基因库 bank ，记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成目标变化，返回 -1 。
注意： 起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
解题思路
BFS 队列 + 字符替换搜素。
- BFS 查找最短路径。
- 每一层尝试将当前字符串的 8 个位置，分别替换为 'A', 'C', 'G', 'T'。
- 检查生成的新基因是否存在于基因库中且未被访问。
Java 代码实现
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> set = new HashSet<>(Arrays.asList(bank));
if (!set.contains(endGene)) return -1;
Queue<String> q = new LinkedList<>();
q.offer(startGene);
int steps = 0;
char[] genes = {'A', 'C', 'G', 'T'};
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
if (cur.equals(endGene)) return steps;
char[] curArr = cur.toCharArray();
for (int j = 0; j < 8; j++) {
char old = curArr[j];
for (char g : genes) {
curArr[j] = g;
String next = new String(curArr);
if (set.remove(next)) q.offer(next);
}
curArr[j] = old;
}
}
steps++;
}
return -1;
}
}
127. 单词接龙 (Word Ladder)
题目描述
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
解题思路
BFS 队列 + 字典加速查找。
- 使用
HashSet存储wordList以便 O(1) 查找。 - BFS 每一层代表转换了一次。
- 弹出单词，尝试改变其每一个位置的字母（'a'-'z'），如果得到的新单词在
HashSet中，则加入队列并从HashSet中移除（代表已访问）。
Java 代码实现
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int distance = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(endWord)) return distance;
char[] chars = word.toCharArray();
for (int j = 0; j < chars.length; j++) {
char oldCase = chars[j];
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[j] = ch;
String nextWord = new String(chars);
if (wordSet.contains(nextWord)) {
queue.offer(nextWord);
wordSet.remove(nextWord);
}
}
chars[j] = oldCase;
}
}
distance++;
}
return 0;
}
}